Big-O Complexity Cheat Sheet

What Is Big-O?

Big-O notation describes how an algorithm's runtime or space usage grows as the input size grows. It strips away constants and lower-order terms to focus on the shape of the growth.

O(n) means "scales linearly" — double the input, double the time. O(n²) means "scales quadratically" — double the input, quadruple the time. O(1) means "constant" — input size doesn't matter.

There are actually three notations that people conflate:

• O (Big-O) — upper bound. "At most this bad." This is what interviewers mean 99% of the time.
• Ω (Big-Omega) — lower bound. "At least this much work." Useful for proving optimality.
• Θ (Big-Theta) — tight bound. "Exactly this growth rate." Technically the most precise, but people say "Big-O" when they mean this.

In interviews, nobody cares about the distinction. Just use Big-O and describe the worst case unless asked otherwise.

The Hierarchy (Memorize This)

From fastest to slowest growing. Everything above the line is "good" for interviews; everything below gets you a raised eyebrow.

Growth Rate Comparison

Click a function in the legend to toggle it. Use the scale buttons to zoom into different ranges.

How to Determine Complexity

Forget the formulas. Here's the practical approach: look at the loops, look at the recursion, and count the work.

The Rules

1. Sequential blocks → add. Do A then B? O(A) + O(B) → drop the smaller one.
2. Nested blocks → multiply. For each element, do something? O(outer) × O(inner).
3. Drop constants. O(3n) = O(n). O(n/2) = O(n). Constants don't change the shape.
4. Drop lower-order terms. O(n² + n) = O(n²). The bigger term dominates.
5. Recursive calls → draw the recursion tree. Count total nodes × work per node.

Worked Examples

def find_max(arr):
    maximum = arr[0]        # O(1)
    for x in arr:           # runs n times
        if x > maximum:     # O(1) per iteration
            maximum = x     # O(1) per iteration
    return maximum

def has_duplicate(arr):
    for i in range(len(arr)):           # n times
        for j in range(i + 1, len(arr)):# n-1, n-2, ... 1 times
            if arr[i] == arr[j]:
                return True
    return False

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:              # how many times?
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1         # eliminate half
        else:
            hi = mid - 1         # eliminate half
    return -1

def two_pointer_sum(arr, target):
    # arr is sorted
    left, right = 0, len(arr) - 1
    while left < right:          # looks like one loop...
        s = arr[left] + arr[right]
        if s == target:
            return (left, right)
        elif s < target:
            left += 1           # left moves right
        else:
            right -= 1          # right moves left
    return None

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # two recursive calls

def find_closest_pair(arr):
    arr.sort()                        # O(n log n)
    min_diff = float('inf')
    for i in range(1, len(arr)):      # O(n)
        diff = arr[i] - arr[i-1]
        min_diff = min(min_diff, diff)
    return min_diff

def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

# Looks O(n), is actually O(n²) in many languages
result = ""
for char in string_of_length_n:
    result += char  # creates a NEW string each time!

Data Structure Operations

Average Case

* amortized average · † given a pointer to the node · ‡ min/max only · m = key length · k = hash functions · α = inverse Ackermann (effectively constant)

Worst Case (When It Matters)

Sorting Algorithms

k = range of values · d = number of digits

Graph Algorithms

V = vertices · E = edges · § depends on heuristic quality

Space Complexity

Time gets all the attention, but space complexity trips people up in interviews just as often. Same Big-O notation, but counting memory instead of operations.

What Counts as "Space"?

You're measuring auxiliary space — extra memory your algorithm uses beyond the input. The input itself doesn't count (unless you're modifying it in place, which might matter for the discussion).

Common Space Gotchas

• Recursion eats stack space. A recursive DFS on a tree uses O(h) stack space where h is the height. For a balanced tree that's O(log n). For a skewed tree? O(n). You just blew your stack.
• Slicing creates copies. In Python, arr[1:] creates a new list of n-1 elements. Do that inside a recursive call and you're allocating O(n) per level, O(n²) total.
• Strings are immutable. Every concatenation allocates a new string. Building a string character-by-character in a loop is O(n²) space and time.
• Sorting might not be "free." Merge sort needs O(n) extra space. If they say "O(1) extra space," you need heap sort or an in-place algorithm.

Space-Time Tradeoffs

Amortized Analysis

Some operations are usually fast but occasionally slow. Amortized analysis averages the cost over a sequence of operations. It's not the same as average case — it's a guarantee over any sequence, not a probabilistic argument.

The Classic Example: Dynamic Array append()

When you append() to a Python list or push_back() in C++, most of the time it's O(1) — just write to the next slot. But when the array is full, it allocates a new array (typically 2x the size) and copies everything over. That single resize is O(n).

So is append O(1) or O(n)? It's O(1) amortized. Here's why:

Starting with capacity 1, doubling each time:

Insert #1: capacity 1→2, copy 1 element    → 1 work
Insert #2: no resize                        → 1 work
Insert #3: capacity 2→4, copy 2 elements    → 2 work
Insert #4: no resize                        → 1 work
Insert #5: capacity 4→8, copy 4 elements    → 4 work
Insert #6-8: no resize                      → 1 work each

After n inserts: total copies = 1+2+4+...+n ≈ 2n
Average per insert: 2n/n = 2 = O(1)

The expensive resizes happen so rarely that they get "absorbed" by all the cheap inserts. This is the banker's method — each cheap insert "pays" a little extra into a bank, and when the expensive operation hits, there's enough saved up to cover it.

Other Amortized O(1) Operations

• Hash map insert — usually O(1), but occasionally triggers a resize + rehash of all elements
• Union-Find with path compression — individual find can be O(log n), but any sequence of m operations is O(m·α(n)) total, so O(α(n)) amortized (basically constant)
• Splay tree operations — individual ops can be O(n), but any sequence of m ops is O(m log n) total

Common Complexity Mistakes

These trip up everyone — from beginners to people who should know better. Don't be embarrassed if you've made them; just stop making them.

Rules of Thumb

Quick Constraint → Complexity Decoder

When you read a problem on LeetCode and see the constraints section, here's your instant filter:

• Constraint says n ≤ 10⁵ and the output is one number? → O(n) or O(n log n). Think hash map, sorting, two pointers.
• Constraint says n ≤ 10³ and it's a grid/matrix? → O(n²) or O(n² log n). DP on grid, BFS/DFS on matrix.
• Constraint says n ≤ 20? → They want bitmask DP or full backtracking. Small n = brute force is fine.
• Constraint says n ≤ 10⁹? → O(log n) or O(1). Math or binary search. You're not iterating over that.
• Two constraints, like n ≤ 10⁵ and k ≤ 10? → The answer is probably O(n·k). Think about what k parameterizes.