Python Built-in Time Complexity: The Interview Cheat Sheet

You are fifteen minutes into a coding interview. Your solution looks correct. You write if x in my_list and start explaining your logic. The interviewer asks about time complexity. You say O(1).

Wrong. One word, list instead of set, just cost you the round.

Python hides a surprising amount of complexity behind syntax that looks completely innocent. This reference covers every built-in data structure, every operation that matters in interviews, and the exact traps that send otherwise competent engineers home with a rejection.

Python Built-in Time Complexity: Quick Reference

Operation	Container	Complexity	Notes
`x in s`	`list`	O(n)	Linear scan
`x in s`	`set` / `dict`	O(1) avg	Hash lookup
`s.append(x)`	`list`	O(1) amortized	Occasional resize
`s.insert(0, x)`	`list`	O(n)	Shifts every element
`s.pop()`	`list`	O(1)	Removes last
`s.pop(0)`	`list`	O(n)	Shifts every element
`s.pop(i)`	`list`	O(n)	Shifts elements after i
`s[i]`	`list`	O(1)	Direct index
`s[i:j]`	`list`	O(j - i)	Copies a new list
`len(s)`	list / dict / set	O(1)	Stored as a field
`sorted(s)`	any iterable	O(n log n)	Creates a new list
`s.sort()`	`list`	O(n log n)	In-place Timsort
`d.get(k)`	`dict`	O(1) avg	Hash lookup
`d[k] = v`	`dict`	O(1) avg	Hash insert
`s.add(x)`	`set`	O(1) avg	Hash insert
`s.appendleft(x)`	`deque`	O(1)	Use instead of insert(0, ...)
`s.popleft()`	`deque`	O(1)	Use instead of pop(0)
`heappush(h, x)`	`heapq`	O(log n)
`heappop(h)`	`heapq`	O(log n)	Always removes minimum
`heapify(h)`	`heapq`	O(n)	Build heap from list
`"".join(lst)`	`str`	O(n)	The correct way to build strings
`s + t` in a loop	`str`	O(n²)	Classic interview bug

List: The O(n) Traps Nobody Warned You About

Python's list is a dynamic array under the hood. Random access is O(1). Appending to the end is O(1) amortized, because the runtime occasionally doubles the capacity and copies everything over. Those costs spread across many operations, so each individual append stays cheap on average.

The two operations that end interviews: pop(0) and insert(0, x), both O(n). Every element after the target position shifts by one slot. On a million-item list, that is a million memory moves per call, silently, while you nod at the interviewer and explain that your solution is definitely linear.

# Both are O(n). Do not put these in hot loops.
items.insert(0, new_item)   # O(n)
items.pop(0)                # O(n)

# Use collections.deque instead.
from collections import deque
q = deque(items)
q.appendleft(new_item)      # O(1)
q.popleft()                 # O(1)

list.insert(0, x) forces every element to shift right one slot; deque.appendleft adds in O(1) with nothing moving

The membership test x in my_list is a linear scan. If you check membership more than once, convert to a set first. The conversion is O(n), but every subsequent lookup drops to O(1) average. The interviewer will notice if you skip that step.

Slicing bites people who write s = s[1:] inside a loop. Each iteration allocates a new list and copies j - i elements. Do that on every pass and you have turned an O(n) loop into O(n²). Use an index pointer instead.

min() and max() scan every element. If you call either repeatedly on a changing dataset, you want a heap, not repeated full scans.

Dict and Set: "O(1) Average" Means Something Specific

Both dict and set use hash tables internally. Average-case lookup, insert, and membership are O(1). Worst case, when many keys hash into the same bucket, is O(n). In practice, Python's hash function is well-designed and you will not hit worst case on a typical interview problem.

What interviewers want to hear: "O(1) average, O(n) worst case due to hash collisions." Say that instead of just "O(1)" and you sound like someone who has actually read about the data structure rather than someone who saw it on a blog post once.

seen = set()
seen.add(x)           # O(1) avg
if x in seen: ...     # O(1) avg
seen.discard(x)       # O(1) avg

d = {}
d[key] = value        # O(1) avg
v = d.get(key, 0)     # O(1) avg

Set operations across two sets have their own costs. Union a | b is O(m + n). Intersection a & b is O(min(m, n)). Difference a - b is O(m).

Counter from collections is a dict subclass. Construction from an iterable is O(n). most_common(k) runs in O(n log k) using a heap internally, not O(n log n), so it stays efficient when k is small.

String: How to Invent O(n²) With a Plus Sign

Python strings are immutable. This sounds like a language design philosophy point until you understand what it does to your code.

Every time you write result = result + char, Python allocates a new string object, copies the entire old string, and appends the character. In a loop of n iterations, that is 1 + 2 + 3 + ... + n bytes copied. That is O(n²). You have turned a string-building problem into a secretly quadratic one, and it will time out on any input that matters.

Always accumulate string parts in a list and call "".join() at the end. This is the kind of thing that feels like trivia until you fail an interview for it.

# O(n²). This is the classic interview bug.
result = ""
for char in chars:
    result += char

# O(n). Use this every single time.
parts = []
for char in chars:
    parts.append(char)
result = "".join(parts)

str.find(), str.index(), and in on strings are O(n) in the worst case. str.split(), str.strip(), and str.replace() are all O(n). None of these are free, even though they look like single operations.

deque: The Structure That Could Have Saved You

collections.deque is a doubly-linked list of fixed-size memory blocks. Appending or popping from either end is O(1). For BFS queues, sliding window problems, or anything that pops from the front repeatedly, deque is the tool Python actually intended you to use.

from collections import deque
q = deque()
q.append(x)        # O(1) right append
q.appendleft(x)    # O(1) left append
q.pop()            # O(1) right pop
q.popleft()        # O(1) left pop

The tradeoff: d[i] on a deque is O(n). Arbitrary index access requires traversal. If you need fast endpoints and fast random access simultaneously, there is no perfect standard-library structure. A list with a manual index pointer is usually the cleaner interview answer.

heapq: It Is a Min-Heap and It Was Always Going to Be a Min-Heap

Python's heapq module operates on ordinary lists treated as binary heaps. It is always a min-heap. heapq.heappop() removes and returns the smallest element. There is no argument, configuration flag, or trick to change this. The workaround is to push -x and negate the result on pop. This looks mildly unhinged and is completely standard practice.

import heapq

h = []
heapq.heappush(h, 5)    # O(log n)
heapq.heappush(h, 1)    # O(log n)
heapq.heappush(h, 3)    # O(log n)
heapq.heappop(h)        # O(log n), returns 1

# Build from an existing list in O(n).
data = [3, 1, 4, 1, 5, 9]
heapq.heapify(data)

Building a heap by calling heappush n times is O(n log n). Calling heapify on an existing list is O(n). If you already have the data, use heapify. The interviewer may notice. The runtime definitely will.

heapq.nlargest(k, iterable) and nsmallest(k, iterable) run in O(n log k). They are faster than a full sort when k is small relative to n.

Sorting: Timsort Is Good, Also Stable, You Should Know That

list.sort() is in-place, O(n log n), and uses Timsort. sorted() creates a new list, also O(n log n). Both are stable, meaning equal elements preserve their original relative order. This matters when you sort on multiple keys sequentially, and interviewers do ask about it.

nums.sort()                              # in-place, O(n log n)
sorted_nums = sorted(nums)               # new list, O(n log n)
nums.sort(key=lambda x: -x)             # sort descending
nums.sort(key=lambda x: (x[1], x[0]))   # multi-key sort

Timsort exploits already-sorted runs in the data. On nearly sorted input it can approach O(n). On random input it stays at O(n log n). The key= argument runs in O(n) to compute all keys before comparisons. The total cost stays O(n log n).

If your values are bounded integers, say 0 to 100,000, counting sort finishes in O(n + k) and beats Timsort handily. The standard library does not include it, but the problem constraints usually hint at when you need it.

Five Patterns That Reveal Whether You Know This Stuff

These come up in sliding window problems, BFS queue management, string manipulation, and top-k problems. The bread and butter of medium-difficulty interviews:

if x in my_list: Check membership more than once? Convert to a set first.
my_list.pop(0) or my_list.insert(0, x): Switch to collections.deque and use popleft() or appendleft().
result += char in a loop: Buffer parts in a list and call "".join() once at the end.
s = s[1:] in a loop: Each slice allocates a new list. Use an integer index pointer instead.
Calling min() or max() repeatedly on a changing list: Maintain a heap rather than scanning every time.

Each one represents the gap between the O(n) solution the interviewer expected and the O(n²) solution you submitted. Getting any of these wrong signals something specific about how you reason about code, and interviewers write that down.

Where Knowing the Table Is Not Enough

Memorizing this reference is necessary but not sufficient. Interviewers listen for the distinction between O(1) average and O(1) worst case, between amortized and per-operation guarantees, and for whether you instinctively reach for a set instead of a list when membership tests stack up.

That kind of fluency comes from speaking through problems out loud, not from reading tables silently. If you want to build the habit before your next interview, SpaceComplexity runs voice-based mock interviews with rubric feedback across problem-solving, communication, and technical depth. You will hear yourself say "O(1)" when the answer is O(n) and get corrected before it counts.

For the internals that make dict and set fast, the post on hash map time complexity covers the full analysis. Dynamic array time complexity walks through the amortized proof for list.append. If you are deciding between a list and a deque for a specific problem, array vs linked list performance explains the cache behavior that determines real-world speed beyond Big-O.

Eight Rules Before You Code

x in list is O(n). x in set is O(1) average. Choose deliberately.
list.pop(0) and list.insert(0, x) are O(n). Use deque.popleft() and deque.appendleft() for O(1).
String concatenation in a loop is O(n²). Collect parts in a list and use "".join().
heapq is always a min-heap. Negate values for max-heap behavior.
heapify() is O(n). Pushing n items one by one is O(n log n). Use heapify when you have the data upfront.
sorted() and .sort() are both O(n log n) Timsort. sorted() returns a new list. .sort() is in-place. Both are stable.
len() on any built-in container is O(1). It is stored as a field, not computed.
dict.get(), dict[k] = v, and k in dict are O(1) average, O(n) worst case.