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.

A linear work model doubles when n doubles; a quadratic model grows fourfold. Big-O gives an asymptotic upper bound, rather than an exact runtime prediction. O(1) bounds work independently of n under the stated operation-cost model.

There are actually three notations that people conflate:

• O (Big-O) — upper bound. "At most this bad." State which input case and assumptions your bound describes.
• Ω (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.

Big-O alone does not specify worst, average, or best case. State the case separately. Use Θ when you have a matching upper and lower bound.

The Hierarchy (Memorize This)

These representative functions are ordered by asymptotic growth. A feasible algorithm depends on input size, constants, output size, and the actual time and memory budget.

Growth Rate Comparison

Toggle functions with the legend buttons. Change the range, then enter n or move across the chart to inspect values. Curves above the vertical scale are clipped; the text readout still shows their values. These are representative functions, not benchmark timings.

How to Determine Complexity

Count the work in loops and recursive calls, including library operations and the cost of each comparison or copy.

The Rules

1. Sequential blocks → add. Do A then B? O(A + B). Keep both terms when A and B are independent input sizes.
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=None):
    if cache is None:
        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]

# Repeated copying can require O(n²) total work
result = ""
for char in string_of_length_n:
    result += char  # do not rely on an in-place optimization

Data Structure Operations

Average Case

Dynamic-array insertion means append and is amortized. Hash bounds are expected averages under suitable hashing; resize costs are separately amortized. † Linked-list insert/delete assumes the node or required predecessor is known. ‡ Heap access means the root and deletion means extract-root. Trie m = key length; Bloom-filter m = allocated bits and k = hash functions. Union-Find bounds assume both path compression and union by rank/size. Range-tree search means range query; insertion means point update. All bounds assume constant-cost keys/hashes unless noted.

Worst Case (When It Matters)

Sorting Algorithms

k = counting range or radix · d = digits. Space is auxiliary space for the conventional array implementations. Quicksort can bound its stack to O(log n) by recursing only on the smaller partition. Radix stability requires a stable per-digit sort.

Graph Algorithms

V = vertices · E = edges. Adjacency-list input storage is excluded unless the algorithm constructs a copy. Heap-based bounds depend on the queue implementation; a lazy queue can hold O(E) entries. § A* bound shown for a finite graph with a binary heap, nonnegative weights and a consistent heuristic; inconsistent heuristics may require reopening vertices. Heuristic quality affects explored work, not a universal O(E) guarantee. Kosaraju also needs O(V+E) if it builds a reversed graph.

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"?

Auxiliary space measures extra live memory beyond the input. Include the recursion stack and any copies or output buffers, and state whether output storage is excluded. Total space also includes the original input. Modifying an input in place does not itself allocate a copy.

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.
• Separate allocation work from peak space. Repeated prefix copying can take Θ(n²) time and total allocated bytes, while peak live string storage is O(n) when old prefixes are discarded. Retaining every prefix would take O(n²) space.
• 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 (by an implementation-dependent growth factor) 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:

Start empty with capacity 1; double when full:

Insert #1: no resize                       → write 1
Insert #2: capacity 1→2                    → copy 1 + write 1
Insert #3: capacity 2→4                    → copy 2 + write 1
Insert #4: no resize                       → write 1
Insert #5: capacity 4→8                    → copy 4 + write 1
Insert #6-8: no resize                     → write 1 each

Across n appends: copies = 1 + 2 + 4 + ... < 2n
Writes = n; total work < 3n, or O(1) amortized per append.

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 Bounds

• Hash map insert — expected O(1) with suitable hashing, plus amortized resize work
• Union-Find with path compression and union by rank/size — 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

Constraints suggest approaches to investigate; they do not determine a unique solution:

• 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? → Consider bitmask DP or backtracking, then check the actual branching and time limit.
• 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? → Consider O(n·k), and identify what k controls before choosing an approach.

Implementation references

Language guarantees differ from textbook algorithm names. Check the Python sorting guide, Python string documentation, Java Arrays contract, C++ sorting specification, and Boost A* analysis.