Skip to content
Tutorials Center
My learning

Topics

Lesson 145 of 149 ยท Data Structures and Algorithms

Complexity of Built-in Operations

Learn the Big O cost of Python's built-in operations on list, dict, set, deque, str and heapq, see why some are O(1) and others O(n), and pick the right type.

Two lines of Python can look almost identical and behave very differently once the data grows. x in items on a list gets slower with every element you add; x in items on a set stays just as fast. items.pop() is instant, but items.pop(0) has to touch every other element. The difference is not a matter of style. It comes from how each built-in type stores its data, and knowing the costs lets you pick the right type before you write the loop.

The searching and sorting lesson introduced Big-O notation for algorithms you write yourself. This lesson applies the same idea to the operations Python gives you for free. You'll get a table of costs for list, dict, set, deque, str and heapq, learn the reasons behind the numbers, and run small experiments that count the work instead of timing it, so the results are the same on every machine.

The costs below describe CPython, the standard implementation. The Python language itself doesn't promise them, but every mainstream implementation behaves very similarly, and the standard library docs treat these costs as part of the contract in practice.

Reading the numbers

Big-O describes how the work grows with the size n of the collection. A few extra words you'll see in the tables:

  • O(1) means the cost doesn't depend on n.
  • Amortized O(1) means a single call is occasionally expensive, but spread over many calls the average is constant.
  • Average case means "when the data behaves normally." Hash tables are O(1) on average but can degrade to O(n) in the worst case if many keys collide.
  • k is the size of the second thing involved, such as the slice length or the number of items you add.

Lists

A Python list is a dynamic array: one block of memory holding references to its items, side by side. That layout makes some operations trivial and others expensive.

Operation Cost Why
items[i], items[i] = x O(1) jump straight to the slot
len(items) O(1) the size is stored
items.append(x) amortized O(1) write at the end; occasionally the block grows
items.pop() O(1) remove the last slot
items.pop(0), items.insert(0, x) O(n) every other item shifts one slot
items.insert(i, x), del items[i], items.pop(i) O(n) the items after i shift
x in items, items.index(x), items.count(x), items.remove(x) O(n) a linear scan
items[a:b] O(k) builds a new list of k = b - a items
items.extend(other) or items + other O(k) copies k references
items.copy(), list(items) O(n) copies every reference
items.sort(), sorted(items) O(n log n) Timsort; close to O(n) if the data is already almost sorted
min(items), max(items), sum(items) O(n) look at everything once
flowchart LR
    subgraph Before["Before pop(0)"]
        direction LR
        a0["A"] --- a1["B"] --- a2["C"] --- a3["D"]
    end
    subgraph After["After pop(0)"]
        direction LR
        b0["B"] --- b1["C"] --- b2["D"] --- b3["(free)"]
    end
    Before --> After

Removing the first item forces every remaining item to move one slot to the left, which is why it costs O(n).

Why append is "amortized"

When the block of memory behind a list is full, append has to allocate a bigger one and copy the references over. That single call is O(n). But CPython allocates extra room each time (roughly an eighth more than needed), so the next many appends are free. If you add n items one by one, the total work is proportional to n, and each append averages out to a constant.

Python Appending rarely resizes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Ten thousand appends cause only a small number of resizes, so a growing list stays cheap. That is why building a list with append in a loop is fine, while insert(0, x) in a loop is not.

Dictionaries and sets

A dictionary and a set are hash tables. Python computes hash(key), turns it into a slot number, and looks there. If the slot holds an equal key, you're done; if it holds a different key (a collision), Python probes another slot. With a decent hash function, collisions are rare, and a lookup touches about one slot no matter how many items the table holds.

flowchart LR
    K["key 'pear'"] --> H["hash('pear')"]
    H --> S["slot number"]
    S --> T["hash table"]
    T --> V["value, or the next probe"]

A hash table jumps straight to a slot instead of scanning, which is why lookups don't slow down as the table grows.

Operation Average Worst Notes
d[key], d.get(key), key in d O(1) O(n) worst case needs many colliding keys
d[key] = value, del d[key] O(1) O(n) insertion is amortized (the table resizes now and then)
for key in d O(n) O(n) in insertion order
d.keys(), d.values(), d.items() O(1) O(1) these are views; no copying
d.copy(), dict(d) O(n) O(n)
s.add(x), s.remove(x), x in s O(1) O(n) same hash table idea
a.union(b) (union) O(n + m) O(n + m)
a & b (intersection) O(min(n, m)) O(n ร— m) Python loops over the smaller set
a - b (difference) O(n) O(n ร— m)
a <= b (subset) O(n) O(n ร— m)

Two practical consequences follow. Keys must be hashable (so no lists or dicts as keys), and the hash must agree with equality: two equal keys must have equal hashes. The next experiment counts how many times Python has to call __eq__ to compare keys. With a list, it compares against every item. With a set, the hash narrows the search to about one comparison.

Python Counting comparisons: list vs set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each time n grows tenfold, the list needs ten times more comparisons, and the set needs one. That is O(n) against O(1) in plain numbers.

When hashing goes wrong

The O(1) promise depends on keys spreading out over many slots. If every key has the same hash, every key lands in the same place and the table degrades into a linear scan. You can force this by writing a bad __hash__:

Python A bad hash makes a dict slow

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With the bad hash, doubling n roughly quadruples the comparisons: building the table has become O(nยฒ). Python's built-in types (int, str, tuple of hashables) have good hash functions, so you only meet this problem with your own classes, or when an attacker crafts colliding keys (Python randomizes string hashes per process to defend against that). If you write __eq__ and __hash__ yourself, make sure they use the same fields. The special methods lesson covers the rules.

Deques

A list is slow at the front. The collections.deque (double-ended queue, pronounced "deck") is built for both ends: it stores its items in a linked chain of small blocks, so adding or removing at either end never shifts anything. See the collections lesson for its API.

Operation list deque
add/remove at the right end O(1) O(1)
add/remove at the left end O(n) O(1)
x[i] near the ends O(1) O(1)
x[i] in the middle O(1) O(n)
x in seq O(n) O(n)
rotate(k) n/a O(k)

So the choice depends on what you do. A queue (take from the front, add at the back) wants a deque. Random access by index wants a list. Timing makes the gap visible. Because exact times differ between computers, the program prints only a yes/no comparison:

Python Draining a queue: list vs deque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At 20,000 items the deque is typically tens of times faster, and the gap keeps growing with n. Run it with 200,000 items on your own computer and the list version takes noticeably long, while the deque still finishes in a blink.

Strings and tuples

Strings and tuples are immutable, which affects what "changing" them costs:

Operation Cost Notes
s[i] O(1)
len(s) O(1)
s[a:b] O(k) a new string
s + t O(n + m) a brand-new string; the old ones are untouched
x in s (substring test) O(n) typical fast in practice; the worst case is O(n ร— m)
s.split(), s.upper(), s.replace(a, b) O(n)
"".join(parts) O(total length) one pass
t[i] on a tuple O(1)
x in t O(n) same as a list

The important trap is building a long string with += in a loop. Every concatenation may copy everything built so far, so the total work can grow like O(nยฒ). (CPython has a shortcut that often hides this for simple loops, but you can't count on it everywhere.) Collect the pieces in a list and join once:

Python
# Slow in principle: copies the growing string again and again
text = ""
for word in words:
    text += word + " "

# O(total length): one allocation at the end
text = " ".join(words) + " "

Heaps, sorting and bisect

The heapq module turns a plain list into a priority queue, a structure where the smallest item is always easy to get at. The Python data structures lesson shows how to use it.

Operation Cost
heapq.heappush(heap, x) O(log n)
heapq.heappop(heap) O(log n)
heap[0] (peek at the smallest) O(1)
heapq.heapify(items) O(n)
heapq.nsmallest(k, items) / nlargest(k, items) O(n log k)
sorted(items) O(n log n)
bisect.bisect_left(sorted_items, x) O(log n)
bisect.insort(sorted_items, x) O(n) (finding the spot is O(log n), but inserting shifts items)

Note the useful asymmetry: to get just the 10 largest of a million numbers, heapq.nlargest(10, numbers) beats sorting all of them. And if you add items one at a time and always need the smallest, a heap is O(log n) per step while re-sorting a list each time is O(n log n).

Hidden costs

Some of the most expensive lines in Python look harmless, because the loop is hidden inside a short expression. Watch for these:

  • in on a list or tuple inside a loop. for x in a: if x in b is O(len(a) ร— len(b)) when b is a list. Make b a set first and it becomes O(len(a) + len(b)).
  • Slicing in a loop. items = items[1:] copies the rest of the list on every pass. Use an index, or a deque.
  • list.remove() or list.index() inside a loop is another scan per iteration.
  • sorted() inside a loop. Sort once outside the loop, or use a heap.
  • len() is free. Don't cache it for speed; it's O(1) for every built-in type.

The first one is by far the most common. Here it is with comparisons counted, so you can see the saving exactly:

Python Fixing a quadratic loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions give the same answer, but the list-based one does 65,050 comparisons for what the set does with 100. Building the set once costs O(n), and that cost is repaid immediately.

Choosing a type

When you're not sure which container to use, ask what you do most often:

flowchart TD
    Q["What do you do most?"] --> A["Look things up by key<br/>or test membership"]
    Q --> B["Add/remove at both ends"]
    Q --> C["Keep items in order,<br/>access by position"]
    Q --> D["Always take the smallest<br/>or largest next"]
    A --> A1["dict or set"]
    B --> B1["collections.deque"]
    C --> C1["list"]
    D --> D1["heapq"]

Pick the structure whose cheap operations match your most frequent operations.

There is no best container, only a best match for the access pattern. Also remember that Big-O hides constants: for fewer than a few dozen items, a plain list is often the fastest option, because scanning a handful of items is cheaper than hashing. Use these tables to avoid the O(nยฒ) traps on large inputs, and use measurements (the performance lesson shows how) when the difference is small.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the cost of items.pop(0) on a list with n items?

    A list stores its items side by side, so removing the first item moves all the others one position to the left. Use collections.deque and popleft() for O(1) removal at the front.
  2. 2. Why is x in some_set O(1) on average while x in some_list is O(n)?

    A set is a hash table. The hash of the value points near the right slot, so lookups don't get slower as the set grows. A list has no such index and must scan.
  3. 3. A class defines __hash__ so that it always returns 7, and __eq__ compares by value. What happens to a dictionary that uses its instances as keys?

    A constant hash is legal, since equal objects only need equal hashes, but every key then lands in the same place and Python has to compare against the others. Building the dict becomes O(nยฒ).
  4. 4. Which approach builds a long string from many pieces with the best complexity?

    join measures the pieces once and builds the result in a single pass, O(total length). Repeated concatenation can copy the growing string on every step.
  5. 5. Which container is the best fit for a queue where you add items at the back and take items from the front?

    A deque adds and removes at both ends in O(1). A list is O(n) at the front, a tuple can't change, and a set has no order.

Summary

  • Lists are dynamic arrays: indexing and append/pop() at the end are O(1) (append is amortized), while insert, pop(0), remove, index and in are O(n).
  • Dictionaries and sets are hash tables: get, set, delete and membership are O(1) on average, but a poor __hash__ can push them toward O(n).
  • A deque gives O(1) at both ends but O(n) indexing in the middle; use it for queues.
  • Strings and tuples are immutable: "changing" them builds a new object, so use "".join() instead of += in loops.
  • heapq gives O(log n) push and pop for priority queues; sorted() is O(n log n); bisect searches in O(log n).
  • The classic slowdown is x in some_list inside a loop: convert the list to a set once and the loop becomes linear.

Next: Python Cheat Sheet.