DSA Complexity Cheat Sheet

Every data structure and algorithm has a cost: how its running time and memory usage grow as the input gets bigger. Big-O notation is the shorthand the entire field uses to talk about that growth. This lesson is a reference you can come back to again and again — it collects the complexity of the operations and algorithms covered elsewhere in this course into one place, explains how to read and derive Big-O yourself, and walks through worked examples that measure growth directly instead of just asserting it.

Overview: How Complexity Analysis Works

Big-O describes how the number of basic operations (or bytes of memory) an algorithm uses grows as the input size, usually called n, grows toward infinity. It deliberately ignores constant factors and lower-order terms, because those depend on hardware, language, and implementation details that don’t tell you anything fundamental about the algorithm. O(2n + 5) and O(n) describe the same growth shape, so we always simplify to O(n). What matters is the dominant term as n gets large: an O(n) algorithm eventually beats an O(n^2) algorithm no matter how much slower its constant factor is, because doubling n doubles the work for the linear algorithm but quadruples the work for the quadratic one.

Consider a concrete scenario: you need to repeatedly answer "is this value already in my collection?" If the collection is a Python list, answering that question means scanning element by element in the worst case — O(n) per check. If the collection is a set or dict, the same question is answered by hashing the value and jumping straight to its bucket — O(1) on average. Do that check inside a loop that runs n times and the two choices diverge into O(n^2) total work versus O(n) total work. That single choice of container is one of the most common places real programs accidentally become slow, and it’s exactly the kind of thing this cheat sheet exists to make instantly recognizable.

Complexity is also reported per case: best case (the friendliest possible input), average case (a typical, randomly distributed input), and worst case (the input an adversary would choose to hurt you). Interviews and production code care most about the worst case, because that’s the guarantee you can actually rely on. Some structures, like hash maps, have an excellent average case (O(1)) but a poor theoretical worst case (O(n), if every key collides into the same bucket) — in practice Python’s hashing makes that worst case vanishingly rare, but it’s worth knowing it exists.

Time and Space Complexity

The table below shows how the major complexity classes diverge as n grows — this is the shape you should have memorized, because it’s what makes an O(n log n) sort obviously better than an O(n^2) sort for large inputs, even before you write a line of code.

Big-O Name Operations at n=10 Operations at n=20 Typical example
O(1) Constant 1 1 Hash map lookup, array index access
O(log n) Logarithmic ~3 ~4 Binary search
O(n) Linear 10 20 Linear search, single pass over a list
O(n log n) Linearithmic ~33 ~86 Merge sort, heap sort, Python’s sorted()
O(n^2) Quadratic 100 400 Nested loops, bubble sort, insertion sort
O(2^n) Exponential 1,024 1,048,576 Naive recursive Fibonacci, generating all subsets
O(n!) Factorial 3,628,800 ~2.4 × 10^18 Brute-force permutations (traveling salesman)

Next, the operations you’ll reach for constantly on Python’s built-in containers:

Structure Access by index/key Search (unknown position) Insert Delete Notes
list O(1) O(n) O(1) amortized at the end, O(n) at the front O(n) (remaining elements shift) append() is amortized O(1); insert(0, x) or pop(0) shifts every remaining element
dict / set O(1) average O(1) average O(1) average O(1) average Hash table backed; worst case O(n) under pathological collisions; preserves insertion order (3.7+) — that is not the same as being sorted
collections.deque O(n) for arbitrary index O(n) O(1) at both ends O(1) at both ends Use for queues and stacks instead of list.pop(0), which is O(n)
tuple O(1) O(n) immutable immutable Same access pattern as list, cannot change size or contents after creation

And the algorithms this course covers most often:

Algorithm Time (average) Time (worst) Space Notes
Linear search O(n) O(n) O(1) Works on unsorted data
Binary search O(log n) O(log n) O(1) iterative Requires sorted input
Bubble / insertion sort O(n^2) O(n^2) O(1) Both stable; insertion sort is fast on nearly-sorted data
Merge sort O(n log n) O(n log n) O(n) Stable; good for linked lists and external sorting
Quicksort O(n log n) O(n^2) O(log n) Not stable; worst case with a poor pivot on already-sorted input
sorted() / list.sort() (Timsort) O(n log n) O(n log n) O(n) Stable, adaptive — runs faster on partially-sorted input
BFS / DFS on a graph O(V + E) O(V + E) O(V) V = vertices, E = edges, with an adjacency list

Examples

Tables are useful, but the fastest way to make Big-O concrete is to actually count operations instead of just asserting a formula. The three examples below all print a real operation count so you can see the growth rate with your own eyes.

Example 1: Counting operations in linear vs. quadratic loops

def count_operations_linear(n: int) -> int:
    operations = 0
    for i in range(n):
        operations += 1
    return operations


def count_operations_quadratic(n: int) -> int:
    operations = 0
    for i in range(n):
        for j in range(n):
            operations += 1
    return operations


for n in [5, 10, 20]:
    linear = count_operations_linear(n)
    quadratic = count_operations_quadratic(n)
    print(f"n={n}: linear={linear}, quadratic={quadratic}")

Output:

n=5: linear=5, quadratic=25
n=10: linear=10, quadratic=100
n=20: linear=20, quadratic=400

The linear function does exactly n increments, so its operation count matches n exactly. The quadratic function does n increments for every one of the n outer iterations, so its count is always n * n = n^2. Notice that doubling n from 10 to 20 doubles the linear count but quadruples the quadratic count — that ratio is the fingerprint of O(n^2) growth.

Example 2: Linear search vs. binary search, counted

def linear_search_count(arr: list[int], target: int) -> tuple[int, int]:
    comparisons = 0
    for index, value in enumerate(arr):
        comparisons += 1
        if value == target:
            return index, comparisons
    return -1, comparisons


def binary_search_count(arr: list[int], target: int) -> tuple[int, int]:
    comparisons = 0
    left, right = 0, len(arr) - 1
    while left <= right:
        comparisons += 1
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid, comparisons
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1, comparisons


sorted_numbers = list(range(0, 1000, 2))  # 500 even numbers: 0, 2, 4, ..., 998
target = 998

linear_index, linear_comparisons = linear_search_count(sorted_numbers, target)
binary_index, binary_comparisons = binary_search_count(sorted_numbers, target)

print(f"Linear search found index {linear_index} in {linear_comparisons} comparisons")
print(f"Binary search found index {binary_index} in {binary_comparisons} comparisons")

Output:

Linear search found index 499 in 500 comparisons
Binary search found index 499 in 9 comparisons

sorted_numbers holds 500 even numbers, and the target, 998, sits at the very last index (499) — the worst case for linear search, which is why it needs all 500 comparisons. Binary search instead starts with the whole range and cuts it roughly in half on every comparison: 500 → 250 → 125 → … — needing only 9 comparisons, which lines up with log2(500) ≈ 8.97, rounded up. That gap between 500 and 9 comparisons is O(n) versus O(log n) made visible.

Example 3: Naive recursion vs. memoization

def fib_calls_naive(n: int, call_counter: list[int]) -> int:
    call_counter[0] += 1
    if n <= 1:
        return n
    return fib_calls_naive(n - 1, call_counter) + fib_calls_naive(n - 2, call_counter)


def fib_calls_memoized(n: int, cache: dict[int, int], call_counter: list[int]) -> int:
    call_counter[0] += 1
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    result = fib_calls_memoized(n - 1, cache, call_counter) + fib_calls_memoized(n - 2, cache, call_counter)
    cache[n] = result
    return result


n = 10

naive_counter = [0]
naive_result = fib_calls_naive(n, naive_counter)

memo_counter = [0]
memo_result = fib_calls_memoized(n, {}, memo_counter)

print(f"fib({n}) = {naive_result}, naive calls = {naive_counter[0]}")
print(f"fib({n}) = {memo_result}, memoized calls = {memo_counter[0]}")

Output:

fib(10) = 55, naive calls = 177
fib(10) = 55, memoized calls = 19

Both functions compute the correct answer, fib(10) = 55, but the naive version recomputes the same subproblems over and over — fib(5) gets recomputed from scratch dozens of times inside the call tree — so its call count (177) grows exponentially, O(2^n). The memoized version caches each subproblem’s result the first time it’s computed, so every later request for that same n is an O(1) dictionary lookup instead of a fresh recursive tree; its call count (19) grows linearly, O(n). This is the same idea as choosing a hash set over a list in the first example, applied to recursive subproblems instead of loop iterations.

How It Works Step by Step

To see O(log n) happen mechanically, trace binary search on a sorted 16-element array of odd numbers: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31] (index i holds value 2i + 1), searching for 31 at index 15.

  • Step 1: left=0, right=15. mid = 7, value 15. 15 < 31, so discard indices 0–7 and set left=8.
  • Step 2: left=8, right=15. mid = 11, value 23. 23 < 31, so left=12.
  • Step 3: left=12, right=15. mid = 13, value 27. 27 < 31, so left=14.
  • Step 4: left=14, right=15. mid = 14, value 29. 29 < 31, so left=15.
  • Step 5: left=15, right=15. mid = 15, value 31. Match — return index 15.

Five comparisons against 16 elements. Each step throws away roughly half of the remaining candidates, so the number of steps needed is bounded by how many times you can halve 16 before reaching a single element — log2(16) = 4, plus one final comparison to confirm the match, giving the observed worst case of 5. That halving is precisely why binary search requires sorted input: the decision to discard the left or right half only makes sense if you already know every element on one side is smaller (or larger) than the target.

Common Mistakes

Mistake 1: Treating list membership like set membership

A very common way to accidentally write an O(n^2) algorithm is checking in against a growing list inside a loop, not realizing each check itself costs O(n):

def has_duplicates_slow(items: list[int]) -> bool:
    seen = []
    for item in items:
        if item in seen:
            return True
        seen.append(item)
    return False


numbers = [4, 2, 7, 2, 9]
print(has_duplicates_slow(numbers))

Output:

True

This gets the right answer here, but if item in seen scans the entire seen list every iteration, so for n unique items before a duplicate the total work is O(n^2). Swapping the list for a set keeps the logic identical but makes each membership check O(1) on average, dropping the total to O(n):

def has_duplicates_fast(items: list[int]) -> bool:
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False


numbers = [4, 2, 7, 2, 9]
print(has_duplicates_fast(numbers))

Output:

True

Mistake 2: Building strings with repeated concatenation

Strings in Python are immutable, so result += word doesn’t append in place — it allocates a brand-new string and copies everything so far into it. Doing that inside a loop turns what looks like a simple pass into O(n^2) total copying:

def build_string_slow(words: list[str]) -> str:
    result = ""
    for word in words:
        result += word
    return result


print(build_string_slow(["fast", "hash", "lookups", "matter"]))

Output:

fasthashlookupsmatter

The fix is to accumulate pieces in a list (append is amortized O(1)) and join once at the end, which builds the final string in a single O(n) pass:

def build_string_fast(words: list[str]) -> str:
    return "".join(words)


print(build_string_fast(["fast", "hash", "lookups", "matter"]))

Output:

fasthashlookupsmatter

Mistake 3: Assuming a shrinking inner loop means linear time

It’s tempting to look at a nested loop where the inner loop gets shorter each time and assume the total work is O(n) because "it’s not doing the full n every time." It’s still quadratic:

def count_pairs(n: int) -> int:
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            count += 1
    return count


for n in [4, 8, 16]:
    print(f"n={n}: pairs={count_pairs(n)}")

Output:

n=4: pairs=6
n=8: pairs=28
n=16: pairs=120

The inner loop shrinks from n-1 down to 0 as i increases, and summing (n-1) + (n-2) + ... + 0 gives n(n-1)/2 — still quadratic once you drop the constant factor of 1/2. Doubling n from 8 to 16 roughly quadruples the count (28 → 120, close to 4×), which is exactly the O(n^2) signature, not O(n).

Best Practices

  • Always state complexity in terms of a named variable (n, or V/E for graphs) — "it’s fast" or a bare "O(n)" without saying what n measures is not a complete answer.
  • Reach for dict/set the moment you catch yourself writing if x in some_list inside a loop — that pattern is the single most common accidental O(n^2).
  • Build strings with a list plus "".join() instead of repeated += when the number of pieces isn’t tiny and fixed.
  • Use collections.deque instead of list whenever you need to push or pop from the front — list.pop(0) is O(n), deque.popleft() is O(1).
  • Prefer the worst case when reasoning about correctness and reliability; use the average case only when you also understand what makes the worst case rare in your context.
  • Trade space for time deliberately: a hash set, a memoization cache, or a precomputed lookup table all spend O(n) extra memory to turn repeated O(n) work into O(1) work.
  • Don’t over-optimize a piece of code that runs once on ten items — profile or reason about complexity where it actually matters: hot loops, large inputs, or code that will scale with user growth.
  • When comparing algorithms for an interview or a design decision, sketch the growth table (like the ones above) for a couple of concrete n values — it makes the tradeoff visceral instead of abstract.

Practice Exercises

  • Two Sum, two ways. Given a list of integers and a target sum, write a brute-force solution that checks every pair (O(n^2) time, O(1) space), then rewrite it using a single pass with a set or dict that remembers numbers seen so far (O(n) time, O(n) space). Hint: for each number x, check whether target - x has already been seen before adding x itself.
  • Name the complexity. For each shape below, state the Big-O in terms of n and justify it in one sentence: (a) a single loop from 0 to n; (b) a loop from 0 to n where each iteration does a membership check against a plain Python list of length n; (c) two nested loops where the outer runs n times but the inner always runs exactly 5 times regardless of n. (Answers: (a) O(n); (b) O(n^2), since an O(n) check runs n times; (c) O(n), since 5 is a constant factor, not a function of n.)
  • Measure it yourself. Take the build_string_slow and build_string_fast functions from the Common Mistakes section and imagine running both on a list of 100,000 words instead of four. Explain in your own words, referencing how many characters get copied in total, why the gap between them would become dramatically more visible at that size than it is at n=4.

Summary

  • Big-O describes how time or space grows with input size n, ignoring constants and lower-order terms — always name what n represents.
  • list gives O(1) index access but O(n) search and front insertion/deletion; dict/set give O(1) average access, search, insert, and delete via hashing.
  • Linear search is O(n); binary search is O(log n) but requires sorted input, since it relies on discarding half the remaining candidates each step.
  • Comparison sorts bottom out at O(n log n) (merge sort, Timsort); naive quadratic sorts (bubble, insertion) are O(n^2) but insertion sort is fast on nearly-sorted data.
  • Naive recursion without memoization can blow up to O(2^n); caching subproblem results brings many of those down to O(n) at the cost of O(n) extra space.
  • The most common real-world mistakes are: list membership checks masquerading as O(1), repeated string concatenation hiding O(n^2) copying, and misjudging a shrinking nested loop as linear when it’s still quadratic.