Complexity and Performance of Python Operations

Choosing the right built-in matters as much as choosing the right algorithm. A correct solution can still time out if it pops from the front of a list in a loop or rebuilds a string one character at a time. This page maps common Python operations to their time complexity and shows the traps that quietly turn O(n) code into O(n squared).

Pair this page with the Big-O cheat sheet, which covers the notation itself. Here we focus on what specific Python operations actually cost.

Lists: fast at the end, slow at the front#

A Python list is a dynamic array. Appending and popping at the end are amortized O(1), but inserting or removing at the front shifts every other element, which is O(n).

 1data = [1, 2, 3, 4, 5]
 2
 3data.append(6)     # O(1) amortized
 4data.pop()         # O(1)  removes from the end
 5
 6data.insert(0, 0)  # O(n)  every element shifts right
 7data.pop(0)        # O(n)  every element shifts left
 8
 9x = data[3]        # O(1)  indexing is direct
10found = 4 in data  # O(n)  membership scans the whole list

Doing data.pop(0) inside a loop is a classic mistake: n pops of O(n) each gives O(n squared) overall.

deque: O(1) at both ends#

When you need a queue, use collections.deque. It adds and removes from either end in O(1), so it is the correct structure for breadth-first search and sliding windows.

1from collections import deque
2
3queue = deque([1, 2, 3])
4queue.appendleft(0)   # O(1), unlike list.insert(0, ...)
5queue.popleft()       # O(1), unlike list.pop(0)
6queue.append(4)       # O(1)
7print(queue)          # deque([1, 2, 3, 4])

The trade-off: deque does not support fast random access by index. queue[k] is O(n) for a middle index, so use a list when you need indexing and a deque when you need both ends.

Dicts and sets: O(1) average lookups#

Dicts and sets are hash tables. Membership tests, insertions, and deletions are O(1) on average. This is why converting a list to a set before repeated lookups is one of the highest-value optimizations you can make.

 1nums = list(range(1000000))
 2
 3# O(n) per check, O(n squared) if done in a loop
 4# slow = 999999 in nums
 5
 6lookup = set(nums)
 7print(999999 in lookup)   # O(1) average
 8
 9# Dict lookups are O(1) too
10prices = {"apple": 3, "pear": 2}
11print(prices.get("apple"))   # O(1)
12print("pear" in prices)      # O(1)

The “average” caveat matters: in rare adversarial cases hashing degrades, but for interview and challenge purposes you can treat these as O(1).

Strings are immutable#

A string cannot be changed in place. Every concatenation with + builds a brand new string and copies both operands. Building a string with += inside a loop is therefore O(n squared).

 1# Slow: each += copies the whole accumulated string
 2result = ""
 3for ch in "abcdefg":
 4    result += ch          # O(n squared) over the loop
 5
 6# Fast: collect pieces, then join once (O(n) total)
 7pieces = []
 8for ch in "abcdefg":
 9    pieces.append(ch)
10result = "".join(pieces)
11print(result)   # abcdefg
12
13# join also works directly on a generator or comprehension
14csv = ",".join(str(n) for n in [1, 2, 3])
15print(csv)      # 1,2,3

Always build with a list and "".join(...) at the end. The same applies to slicing: s[::-1] reverses a string but creates a full O(n) copy.

Sorting and copying#

Sorting is O(n log n). Copying a list or slicing it is O(n) because every element is touched.

1data = [3, 1, 2]
2
3data.sort()               # O(n log n), sorts in place
4new = sorted([3, 1, 2])   # O(n log n), returns a new list
5
6copy = data[:]            # O(n) shallow copy
7part = data[1:3]          # O(n) over the slice length

Sort once and reuse the result rather than sorting inside a loop. Sorting by a key, data.sort(key=len), is still O(n log n) as long as the key function is O(1) per item.

Common traps to watch for#

These patterns look harmless but hide a quadratic cost:

 1# TRAP 1: membership on a list inside a loop -> O(n squared)
 2# for item in candidates:
 3#     if item in big_list:   # each check is O(n)
 4#         ...
 5# FIX: build a set once, then check membership in O(1)
 6
 7# TRAP 2: pop(0) or insert(0, ...) in a loop -> O(n squared)
 8# FIX: use a deque
 9
10# TRAP 3: string += in a loop -> O(n squared)
11# FIX: append to a list, then "".join(...)
12
13# TRAP 4: rebuilding a list to remove items while iterating
14# FIX: build a new list with a comprehension
15kept = [x for x in [1, 2, 3, 4] if x % 2 == 0]
16print(kept)   # [2, 4]

A quick reference table#

Where to go next#

Internalize these costs and most timeout problems disappear before you write a single line. Review the Big-O cheat sheet for the underlying notation, keep the standard library structures in mind when you pick a container, and apply all of it while working through the curriculum and the algorithms.