Time Complexities of Python Data Structures

There are four built-in data structures in Python — lists, dictionaries, sets, and tuples. Knowing, or at least being familiar with, the time complexities of the operations associated with each data structure will allow you to judge when your algorithm is getting faster or slower.

For the purpose of this article, we will be discussing each operation’s time complexity in terms of its big O time as the industry has defined it. Here’s a refresher on some of the most common time complexities found in computer science.

Now, let's get into each data structure and their respective time complexities for each operation.

Lists & Tuples:

Assuming a list named lst of length n exists:

Note: tuples have the same operations and complexities

Dictionaries:

Assuming a dictionary named dict of length n exists:

Note: defaultdics have same complexities

Sets:

Assuming a set named s of length n exists and s1 and s2 exist:

Note: frozen sets have the same complexities