Time & Space Complexity
The visual guide to analyzing algorithm efficiency — Big O notation, recursion trees, and complexity for every interview pattern.
Complexity analysis answers: how does runtime (or memory) grow as input size grows? We express this with Big O notation.
nThe input size — array length, node count, string length, etc.
T(n)The exact number of operations as a function of n
O(f(n))Upper bound — T(n) grows no faster than f(n) times a constant
Best case ΩLower bound on runtime — the algorithm is at least this fast
Average ΘTight bound — the algorithm runs in exactly this class on average
Worst case OUpper bound — interviews always ask for this one
Actual Operation Counts for Common Input Sizes
| n | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) |
|---|---|---|---|---|---|
| 10 | 3 | 10 | 33 | 100 | ~1K |
| 100 | 7 | 100 | 664 | ~10K | ∞ |
| 1,000 | 10 | 1,000 | ~10K | ~1000K | ∞ |
| 10,000 | 13 | ~10K | ~133K | ~100M | ∞ |
| 1,000,000 | 20 | ~1000K | ~20M | ~1000B | ∞ |
| ■ < 10M ops — fast■ 10M–100M — approaching limit■ 100M–1B — probably TLE■ > 1B — TLE | |||||
Bar width represents relative "slowness" on a log scale for n = 10,000. The longer the bar, the more operations.
O(1)Constant — array index, hash map get/set, stack push/popO(log n)Logarithmic — binary search, balanced BST, heap push/popO(n)Linear — single loop, BFS/DFS, linear scanO(n log n)Linearithmic — merge sort, heap sort, most built-in sortsO(n²)Quadratic — nested loops over same input, bubble sortO(n³)Cubic — triple nested loops, Floyd-Warshall (dense graph)O(2ⁿ)Exponential — all subsets enumeration (brute force)O(n!)Factorial — all permutations (brute force TSP)Drop Constants
Multiplicative constants are dropped. Hardware absorbs constants; Big O cares only about growth shape.
# Two separate loops → 2n → O(n) (NOT O(2n))
for i in range(n):
do_a(i)
for i in range(n):
do_b(i)
# 100 constant ops inside a loop → still O(n)
for i in range(n):
x = a + b # O(1)
y = c * d # O(1)
# ... 98 more O(1) operationsDrop Lower-Order Terms
Keep only the dominant term. For large n, n² completely dwarfs n.
O(n² + n) → O(n²)
O(n log n + n) → O(n log n)
O(2ⁿ + n³) → O(2ⁿ)
O(500) → O(1)
# In code:
for i in range(n): # O(n²) — dominant
for j in range(n):
process(i, j)
for k in range(n): # + O(n) — dropped
scan(k)
# Total: O(n²)Sequential → Add. Nested → Multiply.
# O(n) + O(m) = O(n + m)
def two_arrays(a, b):
for x in a: # O(n)
print(x)
for y in b: # O(m)
print(y)
# → O(n + m) (keep both!)# O(n) × O(m) = O(n·m)
def pairs(a, b):
for x in a: # O(n)
for y in b: # × O(m)
print(x, y)
# → O(n·m)O(n + m) or O(n·m) — never collapse to O(n²)unless you know n = m.Recursion = Work per Call × Number of Calls
Draw the recursion tree. Count nodes (calls) × work per node.
# Each call spawns 2 more → binary tree of calls
# Tree has ≈ 2ⁿ nodes, O(1) work each → O(2ⁿ)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2) # 2 callsMerge sort splits the array in half each time (producing log n levels), then merges each level back together — doing O(n) total work per level.
Levels in tree
log₂n = log₂8 = 3
Work per level
O(n) merge ops
Total
O(n) × log n = O(n log n)
O(n)O(1)Each pointer moves at most n steps. Even with both moving, combined steps ≤ 2n. Drop the constant → O(n).
O(n)O(k)right advances n times, left advances at most n times total. Each element enters and leaves the window once.
O(log n)O(1)Each comparison halves the remaining space. Starting at n, after k steps we have n/2^k elements. k = log₂n when that reaches 1.
O(n) build + O(1) queryO(n)One pass to build. Any range sum [i,j] = prefix[j] − prefix[i−1] — a single subtraction.
O(n)O(n)Every element is pushed once and popped at most once. Total push + pop operations = 2n.
O(n log k)O(k)Each of n elements is pushed into a k-sized heap. Heap push/pop = O(log k). Total: n × log k.
O(V + E)O(V)Each vertex visited once (O(V)). Each edge inspected once from both endpoints (O(E)). Queue holds at most O(V).
O(n)O(h) stackEvery node visited once. Stack depth = tree height h. Balanced: h = O(log n). Skewed: h = O(n).
O(n log n)O(n)log n levels of recursion. O(n) merge work per level. Python's sorted() is Timsort — same bound.
O(n)O(n)→O(1)Fill n states, each O(1). Rolling array optimization: drop space to O(1) when only previous 1–2 states needed.
O(m × n)O(mn)→O(n)Fill every cell in m×n table. Rolling rows reduces space to O(n).
O(bᵈ)O(d)b = branching factor, d = depth. Pruning reduces the constant but not the worst-case class.
O(α(n)) ≈ O(1)O(n)With path compression + union by rank, α(n) < 5 for any practical n (inverse Ackermann function).
O(V + E)O(V + E)Same analysis as BFS — each vertex and edge processed exactly once via Kahn's algorithm.
O(n log n)O(n)Sort by start time (O(n log n)) then one linear pass to merge/process (O(n)). Dominated by sort.
Space complexity counts all memory your algorithm allocates, excluding the read-only input (unless explicitly storing it).
Variables & Primitives
Each int, bool, pointer = O(1)
Call Stack
Each recursive frame counts. Depth h → O(h) space
Data Structures
Arrays, sets, maps, queues you create — count their size
Output Space
Often excluded from auxiliary analysis — ask your interviewer
# RECURSIVE factorial
# Time: O(n) · Space: O(n) — n frames on call stack
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n - 1) # stack grows with each call
# ITERATIVE factorial
# Time: O(n) · Space: O(1) — single variable, no stack growth
def factorial_iterative(n):
result = 1
for value in range(2, n + 1):
result *= value
return result
# DFS on balanced tree of height h = log n
# Time: O(n) · Space: O(log n) — call stack = height
def dfs(node):
if node is None:
return 0
return 1 + dfs(node.left) + dfs(node.right)- 1
Identify input variables
Name them: n = array length, m = string length, V = vertices, E = edges. Keep separate variables for separate inputs.
- 2
Find every loop and recursive call
Mark each loop with how many times it runs in terms of your variables. Nested → multiply. Sequential → add.
- 3
Cost of inner work
Is inner work O(1)? Does it call sort() → O(n log n)? A set lookup → O(1)? Multiply loop count × inner cost.
- 4
Handle recursion with the tree
Width at each tree level × work per node = cost per level. Sum across log n or n levels.
- 5
Apply the four rules
Drop constants. Drop lower-order terms. Combine with + or ×. Simplify to dominant term.
- 6
Count space separately
List every data structure and call stack depth. Sum them. Drop lower-order space terms too.
def two_sum(nums, target):
# Step 1: n = len(nums)
seen = {} # Space: O(n) — dictionary grows up to n entries
for i, value in enumerate(nums): # Step 2: loop runs n times
complement = target - value # Step 3: O(1) arithmetic
if complement in seen: # O(1) hash lookup
return [seen[complement], i]
seen[value] = i # O(1) hash insert
return [] # Inner work: O(1)
# Time: n × O(1) = O(n)
# Space: O(n) — the dictionaryNever classify a loop by its syntax alone. Track how the control variable changes and count the values it can take. A variable that doubles is logarithmic; a variable that grows by a fixed amount is linear; a variable that resets creates a multiplication.
value = 1
while value < n:
work(value)
value *= 2
# Values: 1, 2, 4, 8, ...
# After k iterations: 2^k >= n → k = O(log n)remaining = n
while remaining > 1:
work(remaining)
remaining //= 3
# n, n/3, n/9, ... → O(log n) iterationsfor i in range(n):
j = i
while j < n:
work(i, j)
j += 1
# Work = n + (n - 1) + ... + 1 = n(n + 1)/2 = O(n²)i = 1
while i * i <= n:
work(i)
i += 1
# The loop stops when i reaches √n → O(√n)left = 0
for right in range(n):
while left < right and invalid(left, right):
left += 1
# right moves n times; left also moves at most n times total.
# Total pointer moves ≤ 2n → O(n), not O(n²).Binary divide + linear combine
O(n log n)T(n) = 2T(n/2) + O(n)Merge sortOne smaller recursive call
O(log n)T(n) = T(n/2) + O(1)Binary searchTwo calls shrinking by one
O(2ⁿ)T(n) = 2T(n − 1) + O(1)Naive FibonacciLinear work at every level
O(n²)T(n) = T(n − 1) + O(n)Repeated prefix workFor a recurrence, write down the number of recursive calls, the size of each subproblem, and the non-recursive work done in the current call. Then use a recursion tree: add the work across one level, count the number of levels, and multiply when each level has the same cost.
items = []
for value in values:
items.append(value)
# Most append operations cost O(1).
# An occasional resize copies k existing items and costs O(k).
# Across n appends, copied totals are 1 + 2 + 4 + ... + n < 2n.
# Total cost = O(n), so average/amortized append = O(1).def bad_merge_sort(values):
if len(values) <= 1:
return values
mid = len(values) // 2
left = bad_merge_sort(values[:mid]) # slicing copies O(n) here
right = bad_merge_sort(values[mid:]) # slicing copies O(n) here
return merge(left, right) # O(n)
# Recurrence: T(n) = 2T(n/2) + O(n) → O(n log n)
# The slices add O(n) per level, but do not change the class here.
# In a different recursive algorithm, repeated slices can add another factor.String concatenation inside a loop
"result += char" in a loop can be O(n²) — each concat may copy the whole string. Use a list with append() and join() at the end → O(n).
Calling sort() inside a loop
values.sort() inside an n-iteration loop = O(n² log n) total. Pull sorting out of loops.
Assuming list membership is O(1)
value in a list scans linearly → O(n). Convert to a set first for average O(1) lookups.
Treating two different inputs as one
If you take lists A (size n) and B (size m), write O(n + m) or O(n·m), never O(n²) unless you know n = m.
Ignoring slicing cost
values[mid:] creates a new list in O(k), where k is the slice length. Inside recursion it multiplies cost. Use index pointers instead.
Forgetting call stack space
A recursion of depth n uses O(n) call-stack space even if each frame is O(1). Stack overflow is possible for n > ~10,000.
Misidentifying amortized complexity
Array push is O(1) amortized, not always O(1). Resizing is O(n) but spread over n pushes gives O(1) average. Don't count the resize cost per push.
| Operation | Time |
|---|---|
| List index [i] | O(1) |
| list.append() / pop() | O(1) amortized |
| list.insert(0) / pop(0) | O(n) |
| List slice [i:j] | O(j − i) |
| sorted(list) | O(n log n) |
| value in list | O(n) |
| value in set / dict | O(1) avg |
| set.add() / dict[key] = val | O(1) amortized |
| String += char | O(n) per op |
| String slice [i:j] | O(k) |
| Binary search | O(log n) |
| Heap push / pop | O(log n) |
| Build heap from array | O(n) |
| Trie insert / search | O(L) |
| Union-Find find (with PC) | O(α(n)) ≈ O(1) |
| BFS / DFS on graph | O(V + E) |
| Recursive DFS on tree | O(n) time · O(h) space |
Built-in Toolkit & Data Structures
Standard Library| Category | Python pattern | Use it for | Cost |
|---|---|---|---|
| DP / Cache | @cache (or @lru_cache(None)) | Zero-boilerplate DP memoization | O(1) lookup |
| Recursion | sys.setrecursionlimit(200_000) | Prevent stack overflow on deep trees/DFS | O(1) |
| Dict | collections.defaultdict(list) | Graph adjacency list & grouping | O(1) avg |
| Dict | collections.defaultdict(int) | Character & number frequency counting | O(1) avg |
| Dict | collections.Counter(values) | Frequency maps, anagram checks | O(n) build |
| Counter | counts.most_common(k) | Top-k elements via internal heap | O(n log k) |
| Set | seen.add(x) / x in seen | Deduplication and constant-time lookup | O(1) avg |
| Queue | collections.deque(); q.popleft() | BFS & sliding-window (never list.pop(0)!) | O(1) |
| Heap | heapify(nums) | Turn list into min-heap in-place | O(n) |
| Heap | heappush(h, x) / heappop(h) | Priority queue, Dijkstra, Top-K | O(log k) |
| Heap | heappushpop(h, x) | Push then pop smallest in one step | O(log k) |
| Search | bisect_left(arr, x) | First index where element >= x | O(log n) |
| Search | bisect_right(arr, x) | First index where element > x | O(log n) |
| Iteration | for i, val in enumerate(arr) | Index and value together | O(n) |
| Iteration | for a, b in zip(xs, ys) | Parallel walk; stops at shorter array | O(min(n, m)) |
| Matrix | zip(*matrix) | Transpose matrix (turn columns into rows) | O(rows × cols) |
| Sorting | sorted(arr, key=lambda x: (x[0], -x[1])) | Multi-key sort (asc by A, desc by B) | O(n log n) |
| Logic | any(cond(x) for x in arr) | Short-circuit check: True on first match | O(n) worst |
| Logic | all(cond(x) for x in arr) | Short-circuit check: False on first fail | O(n) worst |
| Strings | "".join(char_list) | Join strings (never string += char in loop) | O(n) |
| Strings | s.isalnum() / isalpha() / isdigit() | Validate characters in palindromes | O(len(s)) |
| Strings | s[::-1] / reversed(s) | Reverse string or list | O(n) |
| Math | divmod(a, b) | Returns (a // b, a % b) together | O(1) |
| Math | math.gcd(a, b) / math.lcm(a, b) | Greatest common divisor & LCM | O(log min(a,b)) |
| Math | float("inf") / -float("inf") | Initial min/max distance & DP values | O(1) |
Bit Manipulation Quick Reference
| Operation | Bitwise formula | Interview application |
|---|---|---|
| Check odd / even | x & 1 | Returns 1 if odd, 0 if even |
| Clear lowest set bit | x & (x - 1) | Count set bits in O(k) steps (Brian Kernighan) |
| Isolate lowest set bit | x & -x | Isolates the rightmost 1-bit |
| Check power of two | x > 0 and (x & (x - 1)) == 0 | Powers of 2 have exactly one 1-bit |
| XOR identity | x ^ x == 0 and x ^ 0 == x | Find the Single Number among pairs in O(n) |
| Check k-th bit | (x >> k) & 1 | Inspect state in bitmasks / subset problems |
| Toggle k-th bit | x ^ (1 << k) | Flip bit from 0 to 1 or 1 to 0 |
| Set k-th bit | x | (1 << k) | Turn on state in bitmask DP |
5 Dangerous Python LeetCode Traps
1. The 2D Array Reference Bug
The first line copies row references. Modifying grid[0][0] mutates every single row!
2. Negative Integer Division
Python // rounds toward negative infinity. LeetCode questions (like Evaluate Reverse Polish) expect truncation toward zero.
3. String Concatenation in Loops
Strings are immutable. Repeated += copies the string each time, turning an O(n) loop into O(n²).
4. Recursive Slicing Overhead
Slicing creates a new list in O(k) time and memory. Inside recursion, pass index boundaries instead.
Battle-Tested Interview Templates
from functools import cache
import sys
sys.setrecursionlimit(200_000)
@cache # Automatically memoizes state
def dp(i, target):
if target == 0:
return 0
if i == len(nums) or target < 0:
return float('inf')
take = 1 + dp(i, target - nums[i])
skip = dp(i + 1, target)
return min(take, skip)from bisect import bisect_left, bisect_right arr = [1, 2, 4, 4, 4, 7, 9] # First index >= target (left insertion) idx_l = bisect_left(arr, 4) # -> 2 # First index > target (right insertion) idx_r = bisect_right(arr, 4) # -> 5 # Frequency count in O(log n) freq = idx_r - idx_l # -> 3 # Check target existence in O(log n) exists = idx_l < len(arr) and arr[idx_l] == 4
# Next Greater Element in O(n) time & space
def next_greater(nums):
stack = [] # Monotonic decreasing indices
res = [-1] * len(nums)
for i, num in enumerate(nums):
# Resolve elements smaller than current
while stack and nums[stack[-1]] < num:
prev = stack.pop()
res[prev] = num
stack.append(i)
return res
# Usage: next_greater([2, 1, 2, 4, 3])class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.count = n # Component count
def find(self, x):
# Path compression: O(alpha(n))
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry: return False
self.p[ry] = rx
self.count -= 1; return Truefrom collections import deque
queue = deque([(start_r, start_c)])
seen = {(start_r, start_c)}
DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))
while queue:
r, c = queue.popleft()
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
# Check matrix bounds & unvisited
if 0 <= nr < R and 0 <= nc < C:
if (nr, nc) not in seen:
seen.add((nr, nc))
queue.append((nr, nc))from collections import deque
adj = [[] for _ in range(n)]
deg = [0] * n
for u, v in edges:
adj[u].append(v); deg[v] += 1
q = deque(i for i in range(n) if deg[i] == 0)
order = []
while q:
node = q.popleft()
order.append(node)
for nxt in adj[node]:
deg[nxt] -= 1
if deg[nxt] == 0: q.append(nxt)