Big-O — Complexity Cheat Sheet for Data Structures and Algorithms

What it is

Big-O notation is the standard way to describe how an algorithm's running time or memory grows as its input grows. It expresses an upper bound — O(f(n)) means "the cost is at most some constant times f(n) for all sufficiently large n". The notation is asymptotic: it discards constant factors and lower-order terms, which is exactly what you want when comparing algorithms but exactly what fails you when comparing two O(n) algorithms on a 100-item list. There, the constants matter more than the order.

In day-to-day work, Big-O answers three questions: Will this still be fast on 100× more data? Which data structure should I reach for? Why did this query that used to be instant suddenly take 8 seconds? Treat the table below as a vocabulary — when you see "nested loop over the same list", say "that's O(n^2)" and ask whether it matters at the input sizes you actually care about.

The classes in plain English

A useful intuition: doubling input size multiplies the running time by approximately f(2n) / f(n). For O(n) you double; for O(n²) you quadruple; for O(log n) you add one step; for O(2^n) you square it.

How to compute Big-O from code

Four rules cover ~90% of cases:

1. Sequential statements add: f(n) + g(n) = O(max(f, g)). The dominant term wins.
2. Loops over the input multiply by n (or whatever the loop bound is).
3. Nested loops over the same input are quadratic.
4. Divide and conquer that halves the input each step is logarithmic.

# O(n) — one pass
def total(xs: list[int]) -> int:
    s = 0
    for x in xs:
        s += x
    return s

# O(n^2) — nested pass
def has_dup_pair(xs: list[int]) -> bool:
    for i, a in enumerate(xs):
        for b in xs[i+1:]:
            if a == b: return True
    return False

# O(n) using a hash set
def has_dup_set(xs: list[int]) -> bool:
    seen: set[int] = set()
    for x in xs:
        if x in seen: return True
        seen.add(x)
    return False

# O(log n) — binary search on a sorted list
def bsearch(xs: list[int], target: int) -> int:
    lo, hi = 0, len(xs) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if xs[mid] == target: return mid
        if xs[mid] < target: lo = mid + 1
        else:                hi = mid - 1
    return -1

print(total([1,2,3,4,5]))
print(has_dup_pair([1,2,3,2]))
print(bsearch([1,3,5,7,9,11], 7))

python complexity.py

Output:

15
True
3

Data-structure cheat sheet

Time complexities for the typical operations on the most common data structures. "Avg" assumes uniform hashing and no degenerate input; "Worst" is the contractual upper bound.

Algorithm cheat sheet

Sort and search algorithms — the canonical exam-week table, with the rows that matter in practice highlighted.

Amortized analysis

Some operations are usually fast but occasionally slow. Amortized cost averages the slow cases over many calls. The textbook example is the dynamic array's append: most inserts cost O(1), but when the array is full it doubles capacity and copies — O(n). Averaged over n inserts the total work is O(n), so the amortized cost per insert is O(1).

# Each append is O(1) amortized, even though some specific appends trigger an O(n) resize.
import sys
xs: list[int] = []
prev_cap = sys.getsizeof(xs)
for i in range(20):
    xs.append(i)
    cap = sys.getsizeof(xs)
    if cap != prev_cap:
        print(f"after {i+1} appends, list bytes = {cap}")
        prev_cap = cap

python amortized.py

Output:

after 1 appends, list bytes = 88
after 5 appends, list bytes = 120
after 9 appends, list bytes = 184
after 17 appends, list bytes = 248

CPython grows lists in a ~1.125× pattern, doubling-ish at small sizes. The point is the same — the cost of resizing is paid once per growth, amortized across many O(1) appends.

Amortized analysis matters in practice because:

• Dynamic arrays — appending n items costs O(n) total, not O(n log n).
• Hash tables — most inserts are O(1); the occasional rehash is O(n) but happens rarely.
• Disjoint-set union (path compression + union by rank) — almost O(1) per op.

Space complexity

Space complexity counts the extra memory an algorithm allocates beyond the input. The notation is the same O(...). Three patterns recur:

A specific gotcha: when you read "merge sort is O(n log n)", that is time. Its space is O(n) — it allocates a buffer the size of the input. Quicksort is O(log n) space (recursion depth) when implemented in place.

# Naive fibonacci — O(2^n) time, O(n) space (recursion depth)
def fib_naive(n: int) -> int:
    if n < 2: return n
    return fib_naive(n-1) + fib_naive(n-2)

# Memoized — O(n) time, O(n) space
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    if n < 2: return n
    return fib_memo(n-1) + fib_memo(n-2)

# Iterative — O(n) time, O(1) space
def fib_iter(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

import time
t0 = time.perf_counter(); fib_naive(30); t1 = time.perf_counter()
t2 = time.perf_counter(); fib_memo(500); t3 = time.perf_counter()
t4 = time.perf_counter(); fib_iter(500); t5 = time.perf_counter()
print(f"naive(30)  : {t1-t0:.4f}s")
print(f"memo(500)  : {t3-t2:.6f}s")
print(f"iter(500)  : {t5-t4:.6f}s")

python fib.py

Output:

naive(30)  : 0.2210s
memo(500)  : 0.000183s
iter(500)  : 0.000044s

fib_naive(50) already takes minutes; fib_iter(50_000) is still milliseconds. That is the chasm between O(2^n) and O(n).

Master Theorem — divide-and-conquer in one formula

If T(n) = a·T(n/b) + f(n) (a recursive algorithm splits the problem into a pieces of size n/b and does f(n) work to combine), then:

In practice you memorize three results:

• Merge sort. T(n) = 2·T(n/2) + O(n) → O(n log n) (case 2).
• Binary search. T(n) = T(n/2) + O(1) → O(log n) (case 2 with a=1).
• Strassen matrix multiply. T(n) = 7·T(n/2) + O(n²) → O(n^log₂7) ≈ O(n^2.807) (case 1).

Common Big-O confusions

Python performance notes

Python's standard data structures hide costs that are not visible in source. Cross-check the docs at https://wiki.python.org/moin/TimeComplexity for the canonical CPython numbers.

# The list-concatenation trap
import time

n = 50_000

t0 = time.perf_counter()
s = ""
for i in range(n):
    s += "x"
t1 = time.perf_counter()

t2 = time.perf_counter()
s = "".join("x" for _ in range(n))
t3 = time.perf_counter()

print(f"+= concat : {t1-t0:.4f}s")
print(f"join      : {t3-t2:.4f}s")

python concat.py

Output:

+= concat : 0.0241s
join      : 0.0009s

The += form is O(n²) in the general case because each concatenation copies. CPython has a special-case optimisation for the specific pattern s += t on a sole reference, but it is not portable across PyPy or other interpreters and breaks the moment you alias s.

JavaScript / TypeScript performance notes

V8 / SpiderMonkey / JSC each have their own internal representations for arrays and objects ("packed" arrays vs "dictionary mode"). Big-O on the algorithm is the same, but constants vary by an order of magnitude depending on whether the JIT keeps your array in fast mode.

// O(n) intersection of two arrays using a Set
function intersect(a, b) {
  const seen = new Set(a);          // O(|a|)
  return b.filter((x) => seen.has(x)); // O(|b|)
}

// O(|a|*|b|) naive intersection — quadratic
function intersectNaive(a, b) {
  return b.filter((x) => a.includes(x));
}

const a = Array.from({ length: 50_000 }, (_, i) => i);
const b = Array.from({ length: 50_000 }, (_, i) => i + 25_000);

console.time("set");   intersect(a, b);      console.timeEnd("set");
console.time("naive"); intersectNaive(a, b); console.timeEnd("naive");

node intersect.js

Output:

set: 3.012ms
naive: 4521.778ms

A 1500× speedup from one data-structure change. The Big-O analysis (O(n) vs O(n²)) predicts the gap exactly; the wall clock confirms it.

Recognizing complexity in code

Patterns to read off Big-O at a glance:

# O(1) — fixed amount of work
def first_three(xs): return xs[:3]

# O(n) — single linear pass
def count_evens(xs):
    return sum(1 for x in xs if x % 2 == 0)

# O(n) — two SEPARATE passes (still linear)
def avg_and_max(xs):
    return sum(xs) / len(xs), max(xs)

# O(n log n) — sort, then linear
def has_dup_sort(xs):
    s = sorted(xs)
    return any(s[i] == s[i+1] for i in range(len(s)-1))

# O(n^2) — nested loops over the same input
def all_pairs(xs):
    return [(a, b) for a in xs for b in xs]

# O(n * m) — nested loops over DIFFERENT inputs
def cross(a, b):
    return [(x, y) for x in a for y in b]

# O(log n) — halving each step
def count_halvings(n):
    steps = 0
    while n > 1:
        n //= 2; steps += 1
    return steps

# O(2^n) — branching recursion without memo
def subsets(xs):
    if not xs: return [[]]
    rest = subsets(xs[1:])
    return rest + [[xs[0]] + s for s in rest]

print(count_halvings(1024))
print(len(subsets([1,2,3,4,5])))

python patterns.py

Output:

10
32

DP and memoization

Dynamic programming converts an exponential recursion into a polynomial one by caching subproblem results. The Big-O comes from two numbers: how many distinct subproblems exist, and how much work each one does.

# Longest common subsequence — O(n*m) time, O(n*m) space
def lcs(a: str, b: str) -> int:
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

print(lcs("ACGTGTA", "GTACGTCA"))

python lcs.py

Output:

5

n * m subproblems times O(1) work each gives O(n*m) time. Space can be reduced to O(min(n, m)) by keeping only the two most recent rows.

Hot-loop optimization checklist

When a piece of code is in the hot path and Big-O is right but wall time is wrong, the constants usually come from these places.

1. Reduce work per iteration. Hoist invariants out of the loop. Compute len(xs) once.
2. Choose the right structure. Replace O(n) in list with O(1) in set.
3. Avoid quadratic concatenation. Use "".join (Py), arr.join("") (JS), strings.Builder (Go).
4. Avoid per-iteration allocation. Reuse buffers; pre-size lists with [None] * n.
5. Vectorize. In Python, NumPy/Pandas push the loop into C. In JS, TypedArray and the V8 JIT are sensitive to whether your array stays "packed".
6. Cache. functools.lru_cache, @cache, manual memo dicts.
7. Lazy evaluation. Generators (yield) avoid materialising intermediate lists.
8. Short-circuit. any()/all() stop early; for ... break does the same explicitly.
9. Parallelize once Big-O is right. Parallelism gives constant factors. It does not fix O(n²).

Common pitfalls

• Treating Big-O as a wall-clock metric. Two O(n) algorithms can differ by 50× because of cache behaviour, allocation, or branch prediction. Big-O ranks; the profiler measures.
• Ignoring the size of n. For n ≤ ~20, every reasonable algorithm finishes instantly. Constants and clarity beat asymptotic class.
• Hidden quadratic blowups. for x in xs: if x in list_of_seen: ... — looks linear, is quadratic. Same for s + s + s + ... and arr.unshift in a loop.
• Forgetting the worst case. Quicksort on already-sorted input without a randomized pivot is O(n²). Dict insert with adversarial keys is O(n) per op.
• DP without measuring memory. O(n²) time is often fine; O(n²) memory on a 10⁶ input is 1 TB. Trade rows for columns or compress to two rows.
• Misusing O(n log n) sort when O(n) exists. If you need the k smallest items, heapq.nsmallest is O(n log k). Don't sort the whole array.
• Confusing average and worst. Hash tables are O(1) average, O(n) worst — fine for general code, not fine for security-sensitive code where attackers control keys.
• Counting Big-O when I/O dominates. A 1 ms DB roundtrip in a loop dwarfs any algorithmic constant. Batch queries first.
• Recomputing the same thing. len(xs) inside a Python loop is fast but not free. Computing the same hash, regex, or query inside a loop is much worse.
• Allocation inside tight loops. Each Python list literal or JS {} is an allocation. In hot code, hoist them.

Real-world recipes

Detect duplicates in O(n)

def first_duplicate(xs: list[int]) -> int | None:
    seen: set[int] = set()
    for x in xs:
        if x in seen: return x
        seen.add(x)
    return None

print(first_duplicate([3, 1, 4, 1, 5, 9, 2]))

python first_dup.py

Output:

1

O(n) time, O(n) space — strictly better than sorting (O(n log n)) when you only need to detect, not order.

Top-k with a heap — O(n log k)

import heapq

def top_k(xs: list[int], k: int) -> list[int]:
    return heapq.nlargest(k, xs)

print(top_k([5, 1, 9, 3, 7, 2, 8, 4, 6], 3))

python topk.py

Output:

[9, 8, 7]

For n = 10⁶, k = 10: O(n log k) ≈ 10⁶ · log₂10 ≈ 3.3·10⁶ ops vs O(n log n) ≈ 2·10⁷. Six times faster, all from picking the right structure.

Sliding window — O(n) instead of O(n*k)

# Maximum sum of any contiguous k-element window
def max_window_sum(xs: list[int], k: int) -> int:
    s = sum(xs[:k])
    best = s
    for i in range(k, len(xs)):
        s += xs[i] - xs[i - k]
        best = max(best, s)
    return best

print(max_window_sum([2, 1, 5, 1, 3, 2], 3))

python window.py

Output:

9

A naive approach is O(n*k). Sliding the window saves the redundant work and is O(n).

Two-pointer technique — O(n) for sorted input

def two_sum_sorted(xs: list[int], target: int) -> tuple[int, int] | None:
    lo, hi = 0, len(xs) - 1
    while lo < hi:
        s = xs[lo] + xs[hi]
        if s == target: return (lo, hi)
        if s < target: lo += 1
        else:          hi -= 1
    return None

print(two_sum_sorted([1, 2, 4, 7, 11, 15], 13))

python twosum.py

Output:

(2, 4)

O(n) with two pointers; O(n²) with naive nested loops.

Memoize a slow function

from functools import lru_cache

@lru_cache(maxsize=None)
def edit_distance(a: str, b: str) -> int:
    if not a: return len(b)
    if not b: return len(a)
    if a[0] == b[0]: return edit_distance(a[1:], b[1:])
    return 1 + min(
        edit_distance(a[1:], b),
        edit_distance(a, b[1:]),
        edit_distance(a[1:], b[1:]),
    )

print(edit_distance("kitten", "sitting"))

python edit.py

Output:

3

Without lru_cache, this is exponential. With it, O(n*m) — same as the iterative DP version, fewer lines.

Convert a quadratic loop to linear with a hash map

// Two-sum — unsorted input
function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return null;
}

console.log(twoSum([3, 2, 4, 5], 6));

node twosum.js

Output:

[ 1, 2 ]

A naïve double-loop is O(n²). With a hash map, one pass is O(n).

Profile to verify Big-O

The fastest sanity check: double n and time the algorithm. If time doubles, O(n). Quadruples, O(n²). Adds one tick, O(log n). Stays flat, O(1).

import time

def time_at(n: int, fn) -> float:
    t0 = time.perf_counter()
    fn(n)
    return time.perf_counter() - t0

def linear(n):
    s = 0
    for i in range(n): s += i
    return s

def quadratic(n):
    s = 0
    for i in range(n):
        for j in range(n):
            s += 1
    return s

for n in (1_000, 2_000, 4_000):
    print(f"n={n:>5}  linear={time_at(n, linear):.5f}s  quadratic={time_at(n, quadratic):.5f}s")

python verify.py

Output:

n= 1000  linear=0.00006s  quadratic=0.04231s
n= 2000  linear=0.00011s  quadratic=0.16877s
n= 4000  linear=0.00023s  quadratic=0.67390s

The linear column doubles each row; the quadratic column quadruples. Big-O has just been empirically confirmed in three seconds.

Tips

Memorize three rules: nested loops over the same list are O(n²), halving each step is O(log n), hash-set membership is O(1). Those three cover a startling fraction of day-to-day performance wins.

When you see if x in some_list inside a loop, ask whether some_list should be a set or dict. Three characters of change can turn O(n²) into O(n).

Big-O is a model. The real machine has caches, branch predictors, memory hierarchies, and a JIT. For small n (< ~100), constants dominate; for large n, asymptotics do. Use Big-O to rank; use a profiler to optimize.