Time Complexity of Python Data Structures

The time complexity of Python’s data structures is what decides whether a program finishes in a blink or in an hour. Some operations that look identical are very different in cost: x in my_list checks items one by one (O(n)), while x in my_set jumps straight to the answer (O(1) on average), and list.pop(0) shifts every remaining item (O(n)) while deque.popleft() does not (O(1)).

This page is a practical reference: the cost of the operations you use most, with short demonstrations of the surprising ones. If Big O is new, start with Big O Notation Explained With Python Examples.

Rules of thumb

1. Anything that scans the whole collection (in on a list, remove, index, count, min, max, sum) is O(n).
2. Anything that jumps straight to a position or a key (list index, dict lookup) is O(1).
3. Anything that has to shift or copy items (insert or delete in the middle or at the front of a list, slicing) is O(n).
4. Anything that sorts is O(n log n).

list

A Python list is a dynamic array: a block of memory holding references. That makes reading by position instant, and changing the end cheap, but anything at the front or in the middle expensive, because everything after it has to move:

items = [10, 20, 30, 40]
items.append(50)
print(items.pop())
print(items.pop(0))
items.insert(0, 5)
print(items)
print(30 in items)

Output

50
10
[5, 20, 30, 40]
True

“Amortized O(1)” for append means that an occasional append has to grow the underlying array, which takes longer, but spread across many appends the average cost is constant. The front is a different story. To see how different, compare removing 20,000 items from the front of a list and of a deque. The exact times vary from computer to computer, so this only prints whether the list was more than ten times slower:

import time
from collections import deque

n = 20000
lst = list(range(n))
dq = deque(range(n))

start = time.perf_counter()
for _ in range(n):
    lst.pop(0)
t_list = time.perf_counter() - start

start = time.perf_counter()
for _ in range(n):
    dq.popleft()
t_deque = time.perf_counter() - start

print(len(lst), len(dq))
print(t_list > 10 * t_deque)

Output

0 0
True

On a typical computer the real ratio is far larger than 10, and it gets worse as the list grows.

dict and set

Dictionaries and sets are hash tables. Python turns a key into a number (its hash) and uses it to go almost directly to where the item lives. That is why lookups are fast regardless of size (see Hash Tables in Python: Dict and Set for DSA):

d = {}
d["a"] = 1
print(d.get("a"), "a" in d)
del d["a"]
print(len(d))

Output

1 True
0

The worst case for hash tables is O(n), when many keys collide in the same slot. Python’s hashing makes that very unlikely in practice, which is why people quote O(1). The practical payoff of a set over a list for membership tests is large. Here we look up a value 300 times in a collection of 100,000 items, and print whether the list took more than 20 times as long:

import time

n = 100_000
as_list = list(range(n))
as_set = set(as_list)
targets = [n - 1] * 300

start = time.perf_counter()
for t in targets:
    t in as_list
t_list = time.perf_counter() - start

start = time.perf_counter()
for t in targets:
    t in as_set
t_set = time.perf_counter() - start

print(n - 1 in as_list, n - 1 in as_set)
print(t_list > 20 * t_set)

Output

True True
True

If you do repeated in checks on a big list, converting it to a set first is one of the easiest speed-ups there is. Set operations are shown in more detail in Python List vs Tuple vs Set:

a = {1, 2, 3, 4}
b = {3, 4, 5}
print(a | b, a & b, a - b, a ^ b)
print(a.issubset({1, 2, 3, 4, 5}))

Output

{1, 2, 3, 4, 5} {3, 4} {1, 2} {1, 2, 5}
True

deque

collections.deque (double-ended queue) is built for adding and removing at both ends. It is the right tool for queues, and for sliding-window problems:

from collections import deque

d = deque([1, 2, 3])
d.append(4)
d.appendleft(0)
print(d)
print(d.pop(), d.popleft())
d.rotate(1)
print(d)

Output

deque([0, 1, 2, 3, 4])
4 0
deque([3, 1, 2])

The trade-off is that deque is not good at reading the middle by index. See Queue and Deque in Python Explained.

heapq (heaps)

The heapq module turns a plain list into a priority queue that always gives you the smallest item first:

import heapq

h = []
for x in [5, 1, 8, 3]:
    heapq.heappush(h, x)
print(heapq.heappop(h), heapq.heappop(h))
nums = [9, 4, 7, 1]
heapq.heapify(nums)
print(nums[0])
print(heapq.nsmallest(2, [9, 4, 7, 1]))

Output

1 3
1
[1, 4]

More in Heap and heapq in Python: Priority Queues. For a sorted list, the bisect module finds a position in O(log n), but inserting still costs O(n) because of the shifting:

from bisect import bisect_left, insort

data = [1, 3, 5, 7]
print(bisect_left(data, 5))
insort(data, 4)
print(data)

Output

2
[1, 3, 4, 5, 7]

Strings and tuples

Strings and tuples are immutable, so “changing” one always builds a new object:

• Index: O(1). Slice: O(k) for a slice of k characters. Length: O(1).
• Concatenation a + b: O(len(a) + len(b)), because a new string is created. Doing this repeatedly in a loop can add up to O(n²). Collect the pieces in a list and use "".join(parts) instead, which is O(total length).
• x in s for a substring: roughly linear in the length of the string for typical inputs.
• Tuples: index O(1), in O(n).

parts = ["a", "b", "c"]
print("".join(parts))
s = ""
for p in parts:
    s += p
print(s)

Output

abc
abc

Which structure for which job?

Common mistakes

• Using a list as a queue. pop(0) is O(n). Use deque.
• Repeated in checks on a list. Build a set once, and check against that.
• Slicing inside a loop. items = items[1:] copies everything on each pass.
• Inserting at the front of a big list again and again.
• Building a string with += in a loop when the data is large.
• Sorting inside a loop when you only need the minimum. Use min(), or a heap.

Try it yourself

Work out each answer first, then open the solution.

1. You need to process tasks in the order they arrive, adding new ones at one end and taking from the other. Which structure, and why?

from collections import deque

q = deque()
for x in [1, 2, 3]:
    q.append(x)
print(q.popleft(), q.popleft())

1 2

2. You read one million ids and need to know how many are different. What is the cheapest approach?

seen = set()
for x in [3, 1, 3, 2, 1]:
    seen.add(x)
print(sorted(seen))

[1, 2, 3]

3. What is the cost of items.insert(0, x) on a list of n items, and why?

Try the examples in our free Python compiler.

Frequently asked questions

What is the time complexity of list append in Python?

O(1) amortized. An individual append is usually constant time, and occasionally the list has to grow its storage, but averaged over many appends the cost per append is constant.

What is the time complexity of a dictionary lookup?

O(1) on average. In the very unlikely worst case, with heavy hash collisions, it degrades to O(n).

Is x in list O(n)?

Yes. Python compares against the items one by one until it finds a match or reaches the end. Use a set if you do many membership tests.

Why is list.pop(0) slow?

Removing the first item shifts every remaining item one place left, which takes O(n) time. A collections.deque removes from the front in O(1).

What is the complexity of sorted() in Python?

O(n log n) in the worst case. Python’s sort (Timsort) is also stable, and it is fast on data that is already partly ordered.

Are these complexities guaranteed by the language?

They describe how the standard CPython implementation behaves, and they are widely relied on. The language itself defines the behaviour, and implementations document their costs, so treat them as dependable but implementation-specific.

Related reading

• Big O Notation Explained With Python Examples – what these letters mean.
• Hash Tables in Python: Dict and Set for DSA – how the O(1) lookup works.
• Queue and Deque in Python Explained – the right structure for queues.
• Heap and heapq in Python: Priority Queues – always get the smallest next.