Data Structures & Algorithms Cheatsheet

Complexity and Big-O

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

Notation

Big-O bounds how fast the cost grows as input size n grows. Constants and lower-order terms drop, so O(3n + 50) is O(n).

Notation	Meaning	Reading
O(f)	upper bound	grows no faster than f
Ω(f)	lower bound	grows at least as fast as f
Θ(f)	tight bound	grows exactly like f
o(f)	strict upper	grows strictly slower than f

In interviews "complexity" almost always means worst-case Θ, stated as O. Say both time and space, and say which variable n is when there are two inputs.

Growth Rates

Class	Name	n = 20	n = 1,000	n = 10⁶
O(1)	constant	1	1	1
O(log n)	logarithmic	4	10	20
O(√n)	root	4	32	1,000
O(n)	linear	20	1,000	10⁶
O(n log n)	linearithmic	86	10⁴	2×10⁷
O(n²)	quadratic	400	10⁶	10¹²
O(n³)	cubic	8,000	10⁹	10¹⁸
O(2ⁿ)	exponential	10⁶	huge	huge
O(n!)	factorial	2×10¹⁸	huge	huge

Constraint To Target Complexity

Judges run roughly 10⁸ simple operations per second. Read the constraint and pick the shape before writing code.

Max n	Target	Typical approach
≤ 10	O(n!) · O(2ⁿ · n)	permutations, brute-force backtracking
≤ 20–25	O(2ⁿ)	subset enumeration, bitmask DP
≤ 100	O(n³)	Floyd-Warshall, interval DP
≤ 1,000–5,000	O(n²)	2D DP, pairwise loops
≤ 10⁵–10⁶	O(n log n)	sort, heap, binary search, sweep
≤ 10⁷–10⁸	O(n)	hash map, two pointers, prefix sums
≤ 10¹⁸	O(log n) · O(1)	math, binary search on the answer

Reading Loops

# O(n)
for x in a: ...

# O(n^2)
for i in range(n):
    for j in range(n): ...

# O(n^2) too: n/2 * n on average, constants drop
for i in range(n):
    for j in range(i, n): ...

# O(n log n): outer halves each step, inner is linear
while n > 1:
    for i in range(n): ...
    n //= 2

# O(log n): the loop variable multiplies
i = 1
while i < n:
    i *= 2

Sequential blocks add, so O(n) then O(n log n) is O(n log n). Nested blocks multiply. A recursive call inside a loop multiplies too.

Recurrences And The Master Theorem

For T(n) = a·T(n/b) + O(n^d):

Case	Result	Example
d > log_b a	Θ(n^d)	T(n)=2T(n/2)+n² → Θ(n²)
d = log_b a	Θ(n^d log n)	merge sort, 2T(n/2)+n → Θ(n log n)
d < log_b a	Θ(n^(log_b a))	Karatsuba, 3T(n/2)+n → Θ(n^1.585)

Other recurrences worth memorizing:

T(n) = T(n−1) + O(1) → O(n), simple recursion
T(n) = T(n−1) + O(n) → O(n²), quicksort worst case
T(n) = 2T(n−1) + O(1) → O(2ⁿ), naive Fibonacci or subsets
T(n) = T(n/2) + O(1) → O(log n), binary search

Amortized And Space

Amortized is the average cost per operation across a worst-case sequence, not the average over random inputs. A Python list.append is O(1) amortized: doubling the backing array costs O(n) occasionally, but each element pays O(1) toward its own copy.

Operation	Worst single	Amortized
dynamic array append	O(n)	O(1)
hash map insert	O(n)	O(1)
union-find with path compression	O(log n)	O(α(n)) ≈ O(1)

Space complexity counts the extra memory you allocate, plus the recursion stack. A recursive DFS on a path graph is O(n) space even with no data structures. "In place" means O(1) extra, so a sort that allocates a temporary array of size n is not in place.

Common Traps

Sorting strings. Comparing two length-k strings is O(k), so sorting n of them is O(n·k log n), not O(n log n).
Slicing copies. a[1:] in Python is O(n), so recursing on slices turns O(n) into O(n²). Pass indices instead.
in on a list is O(n). Only set and dict give O(1) membership.
String concatenation in a loop is O(n²) in Python and Java. Collect into a list and "".join(parts), or use StringBuilder.
list.pop(0) is O(n). Use collections.deque.popleft() for O(1).
Output size is a floor. Printing all subsets is at least O(2ⁿ) no matter how clever the search is.