O(1)
Constant time. Runtime does not grow with input size. dict lookup, set membership, list append, and stack push all sit here. Aim for O(1) inside the inner loop of any sort or merge.
Complexity reference · CPython 3.10+
Big-O Cheatsheet for Python Builtins
TAs grade time complexity on every DATA 100, CSE 163, CS50P, and CMU 15-112 assignment that touches a 10000-row dataset. This page lists the average and worst-case Big-O for every operation on list, dict, set, frozenset, str, tuple, collections.deque, and heapq, plus 6 before-and-after snippets for the quadratic patterns students ship by accident.
7 builtin tables CPython average and worst case 6 before / after fixes
Reading the tables
5 complexity classes in 30 seconds
Big-O describes how runtime scales with input size n. The 5 classes below cover almost every Python homework problem. Memorize the shape of each, then read the operation tables like a lookup.
O(log n)
Logarithmic. Doubling the input adds one step. Binary search on a sorted list with bisect.bisect_left, and the heappush and heappop operations from heapq.
O(n)
Linear. Each element touched once. A single pass through a list, the in operator on a list, sum, max, and any list comprehension over the full sequence.
O(n log n)
Linearithmic. The cost of comparison-based sorting. list.sort, sorted, and heapify on an unsorted sequence land here. This is the cheapest sort Python ships.
O(n^2)
Quadratic. A loop inside a loop. list.pop(0) inside a for loop, repeated string concatenation with +=, and naive nested-loop search all degrade to this on a 10000-row dataset.
list
17 list operations with complexity
Python lists are dynamic arrays. Append and index by position are O(1). Anything that touches the front of the list, or scans for a value, costs O(n).
dict
10 dict operations with complexity
Python dicts are open-address hash tables. Average lookup, insert, delete, and membership are O(1). Worst case degrades to O(n) under hash collisions, which CPython mitigates with randomized hash seeds since 3.3.
set and frozenset
10 set operations with complexity
Sets share the dict hash-table backing minus the values. Membership and add are O(1) on average. Convert a list to a set the moment you need more than 3 membership tests against the same data.
str
11 string operations with complexity
Strings in CPython are immutable Unicode. Every concatenation builds a new string. The quadratic trap appears when a student loops += over a long sequence; the linear fix is str.join on a list.
tuple
6 tuple operations with complexity
Tuples share the list array layout but are immutable, which makes them hashable. Use tuples as dict keys and set members when the data is fixed.
collections.deque
8 deque operations with complexity
A deque is a doubly linked list of fixed-size blocks. appendleft and popleft both run in O(1), which is the reason to pick deque over list for any queue, sliding window, or BFS frontier on a 6.006 or DATA 100 assignment.
heapq
7 heapq operations with complexity
heapq turns a list into a min-heap. heappush and heappop run in O(log n). heapify runs in O(n), which beats n separate pushes when you start from a flat list. Dijkstra, A-star, and the top-k pattern all live here.
Common blunders
6 quadratic patterns and their linear fix
These 6 anti-patterns account for most of the time-limit-exceeded marks on the autograded parts of CS50P, CSE 163, DATA 100, and CMU 15-112. Each block shows the slow version, the fix, and the line that changes.
Linear membership on a 10k list
Slow
# x in big_list is O(n) per call
big_list = list(range(100000))
hits = 0
for item in [50, 1000, 99999]:
if item in big_list:
hits += 1
print(hits) # 3, but the inner test scanned 100000 items each time
Fix
# Convert once; membership becomes O(1)
big_list = list(range(100000))
lookup = set(big_list)
hits = sum(1 for item in [50, 1000, 99999] if item in lookup)
print(hits) # 3, three constant-time lookups
list.pop(0) inside a for loop
Slow
# Each pop(0) shifts every remaining element: O(n^2) total
data = list(range(10000))
collected = []
while data:
collected.append(data.pop(0)) # O(n) each iteration
Fix
# collections.deque has O(1) popleft
from collections import deque
data = deque(range(10000))
collected = []
while data:
collected.append(data.popleft()) # O(1) each iteration
Repeated string concatenation
Slow
# += on str inside a loop is O(n^2) over total length
parts = ['line ' + str(i) for i in range(5000)]
result = ''
for p in parts:
result += p # allocates a new string every iteration
Fix
# str.join allocates once
parts = ['line ' + str(i) for i in range(5000)]
result = ''.join(parts) # O(total length), single allocation
Counting with .count() in a loop
Slow
# Each .count() is O(n). Calling it n times yields O(n^2).
words = 'the cat sat on the mat the dog barked'.split() * 1000
freq = {w: words.count(w) for w in set(words)}
print(freq['the'])
Fix
# Counter scans the list once in O(n)
from collections import Counter
words = 'the cat sat on the mat the dog barked'.split() * 1000
freq = Counter(words)
print(freq['the'])
Sorting to find the smallest k items
Slow
# Full sort is O(n log n) when you only want 5 items
nums = list(range(1000000))[::-1]
smallest = sorted(nums)[:5]
print(smallest) # [0, 1, 2, 3, 4]
Fix
# heapq.nsmallest is O(n log k); for k << n this wins
import heapq
nums = list(range(1000000))[::-1]
smallest = heapq.nsmallest(5, nums)
print(smallest) # [0, 1, 2, 3, 4]
Dict key lookup with try / except as control flow
Slow
# Exception handling is expensive when triggered often
counts = {}
for ch in 'abracadabra' * 100:
try:
counts[ch] += 1
except KeyError:
counts[ch] = 1
Fix
# defaultdict avoids the exception path
from collections import defaultdict
counts = defaultdict(int)
for ch in 'abracadabra' * 100:
counts[ch] += 1
Related references
4 references that pair with the Big-O cheatsheet
Python Cheatsheet for University Coursework
Built-ins, control flow, functions, OOP, comprehensions, and stdlib patterns with 35 runnable snippets.
Common Python Errors
Eighteen errors decoded, from IndexError on the wrong slice to RecursionError without a base case.
Python Homework Workflow
The 7-step process from brief to Gradescope, including profiling and complexity review before submit.
Python Debugging Guide
pdb, breakpoint(), logging, and profiling with cProfile. The order TAs expect when you ask for help.
Need a faster Python solution?
Send the brief, get a quote in 15 minutes, and receive Python code profiled against your target complexity. Pay 50% to start, 50% after the autograder passes.