Big O Cheat Sheet 2026: Time and Space Complexity Explained

A Big O cheat sheet is a reference table of the time and space complexity of common data structure operations and algorithms, used to choose and justify solutions in coding interviews. Big O notation describes how runtime or memory grows as input size n grows, keeping only the dominant term and dropping constants. This page gives you the full tables plus a five-step method to derive the complexity of any solution you write.

Key Takeaways

• Most accepted interview solutions are O(n) or O(n log n). Read the input constraints first, because they tell you which class the interviewer expects.
• Hash map operations are O(1) on average and O(n) in the worst case. Say "average" out loud; interviewers notice.
• A nested loop is not automatically O(n squared). If the inner pointer never moves backward, the total work is often O(n), as in sliding window.
• Recursion costs space. A recursive DFS uses O(h) stack space, where h is the recursion depth, even with no extra data structures.
• Amortized O(1) (dynamic array append) is a worst-case guarantee across a sequence, not a probability statement.
• To derive complexity fast: count the work per element, multiply by how many times each element is touched, then add the cost of every library call you used.

What Is Big O Notation?

Big O notation is an upper bound on how an algorithm's cost grows as its input grows. If an algorithm does 3n + 50 steps, its complexity is O(n), because for large n the constant 50 and the multiplier 3 stop mattering.

Textbooks separate Big O (upper bound), Big Omega (lower bound), and Big Theta (tight bound). In interviews, "Big O" usually means the tight worst-case bound.

Two rules cover most simplification:

1. Drop constants. O(2n) is O(n). O(n/2) is O(n).
2. Keep the dominant term. O(n squared + n) is O(n squared). O(n + m) stays as is when n and m are independent inputs.

Common Big O Complexity Classes

These are the classes you will meet in interviews, ordered from fastest to slowest growth. The operation counts for n = 1,000,000 show why the class matters more than micro-optimizations.

Use constraints to predict the target complexity

A widely used rule of thumb is that judges and interview runtimes handle roughly 10^7 to 10^8 simple operations per second. It is an approximation, not a spec, but it turns the constraint line into a hint.

If the problem says n is up to 10^5 and your idea is O(n squared), you need a different idea before you write code. Our coding interview patterns cheat sheet maps those signals to specific techniques.

Data Structure Operations Table

This is the core table. Times are worst case unless marked "avg" (average) or "amort" (amortized). n is the number of elements, L is key or word length.

Three details that come up in follow-ups:

• Building a heap from n items is O(n) with heapify, not O(n log n). Pushing n items one at a time is O(n log n).
• α(n) is the inverse Ackermann function, which is at most 4 or 5 for any input size you will ever see. Treat union-find operations as effectively constant.
• A balanced BST beats a hash map when you need order: floor, ceiling, range queries, or sorted iteration. In Java that is TreeMap; in C++ it is std::map. Python has no built-in balanced BST, so candidates usually reach for bisect on a sorted list (O(log n) search, O(n) insert) or a heap. Our binary tree interview questions guide covers the tree side in depth.

Hidden costs in language built-ins

Library calls look like one step but often are not. These are the ones that most often turn an O(n) solution into O(n squared). The Python wiki's TimeComplexity page documents the CPython numbers.

If you interview in Python, the Python interview questions guide covers more of these gotchas.

Sorting Algorithms Table

Sorting is the most common hidden O(n log n) in interview solutions. Know this table well enough to explain why you would pick one algorithm over another.

Here k is the range of key values and d is the number of digits. Built-in sorts are what you will actually call. Python's sorted and JavaScript's Array.prototype.sort in V8 use Timsort-family algorithms, Java sorts object arrays with a Timsort and primitive arrays with dual-pivot quicksort, and C++ std::sort is typically introsort with an O(n log n) worst case. For interview purposes, state your built-in sort as O(n log n) time.

Space is the part candidates get wrong. Python's list.sort() sorts in place but Timsort can still use up to O(n) auxiliary memory, so calling it "O(1) space" is not accurate.

Algorithm Complexity Reference

Beyond sorting, these are the algorithms whose complexity interviewers expect you to know without thinking.

For more on the graph entries, see the graph algorithms coding interview guide.

How to Derive Complexity in 30 Seconds

Deriving complexity is a counting exercise: how many times is each piece of work done, and what does each piece cost? This five-step method works for nearly every interview solution.

1. Name your variables. n for the main input, m for a second input, V and E for graphs, k for a parameter. Never collapse two inputs into one n.
2. Find the loops and recursion. Mark each loop and each recursive call.
3. Count total iterations, not nesting depth. Ask how many times the innermost line runs across the whole program.
4. Price every library call. Sorting, slicing, in on a list, string concatenation, heap operations.
5. Add sequential parts, multiply nested parts, keep the dominant term. Then do the same for memory, including the call stack.

Worked example 1: the triangle loop

for i in range(n):
    for j in range(i + 1, n):
        check(arr[i], arr[j])

The inner line runs (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 times. Drop the constant and lower term: O(n squared) time, O(1) space.

Worked example 2: the doubling loop

i = 1
while i < n:
    work()
    i *= 2

i takes the values 1, 2, 4, 8, and so on, reaching n after about log2(n) steps. Any loop where the variable multiplies or divides by a constant is O(log n).

Worked example 3: the nested loop that is actually linear

def longest_unique(s):
    seen = set()
    left = best = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

It looks quadratic because of the while inside the for. But left only moves forward and can advance at most n times in total. Each character is added once and removed at most once, so the total work is O(n). Space is O(min(n, alphabet size)) for the set. This argument, called aggregate analysis, is the one interviewers want to hear.

Worked example 4: sort then scan

def has_pair(nums, target):
    nums.sort()
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        total = nums[lo] + nums[hi]
        if total == target:
            return True
        if total < target:
            lo += 1
        else:
            hi -= 1
    return False

Sequential parts add: O(n log n) for the sort plus O(n) for the scan. The dominant term wins, so the answer is O(n log n) time. Space is O(n) auxiliary for Timsort in Python, or O(1) if you are allowed to assume an in-place heapsort.

Worked example 5: two independent inputs

def common(a, b):
    lookup = set(a)
    return [x for x in b if x in lookup]

Building the set is O(n), scanning is O(m) with average O(1) lookups. The answer is O(n + m) time and O(n) space. Writing O(n) here loses information and an interviewer may push back.

How to Analyze Recursion

Recursion complexity equals the number of calls multiplied by the work per call, excluding the recursive calls themselves. Drawing the recursion tree for three levels is usually enough to see the pattern.

The general tool for divide-and-conquer recurrences is the Master Theorem, but in interviews you almost never need its full form. Merge sort is the case to remember: log n levels, O(n) work per level, O(n log n) total.

Memoization changes the count

from functools import lru_cache

def unique_paths(m, n):
    @lru_cache(maxsize=None)
    def go(r, c):
        if r == m - 1 or c == n - 1:
            return 1
        return go(r + 1, c) + go(r, c + 1)
    return go(0, 0)

Without the cache, this branches twice per call and is exponential. With the cache, each (r, c) pair is computed once, so the cost is the number of states times the work per state: O(m * n) time and O(m * n) space for the cache, plus O(m + n) recursion depth. That "states times transitions" formula is how you analyze any DP; the dynamic programming patterns guide applies it to the standard problem families, and the recursion and backtracking guide covers the exponential cases.

What Is Amortized Complexity?

Amortized complexity is the average cost per operation over a worst-case sequence of operations. It lets you say an operation is cheap overall even if it is occasionally expensive, with no probability involved.

The standard example is appending to a dynamic array. When the array is full, it allocates a larger block (growth factors are implementation-specific, typically between 1.125x and 2x) and copies every element, which costs O(n). Because capacity grows geometrically, those copies happen rarely enough that n appends cost O(n) in total, so each append is amortized O(1).

Other amortized results to know:

• Monotonic stack: each element is pushed once and popped at most once, so n operations cost O(n) total even though one pop loop can run long.
• Queue built from two stacks: amortized O(1) per operation, because each element moves between stacks at most once.
• Union-find with path compression and union by rank: amortized O(α(n)) per operation.
• Hash table resizing: the occasional rehash is O(n), but insertion stays O(1) amortized on average.

When an interviewer asks "isn't that pop loop O(n) each time?", the answer is to count total pushes and pops across the run, not per iteration.

How to Calculate Space Complexity

Space complexity measures the extra memory an algorithm uses as a function of input size. Most interviewers mean auxiliary space, which excludes the input itself and usually excludes the output you are required to return. Clarify which one they mean if the answer changes.

Count four sources of memory:

1. Data structures you allocate: sets, maps, arrays, heaps. A hash map with one entry per element is O(n).
2. The call stack: recursion depth times frame size. Recursive DFS on a skewed tree is O(n) space.
3. Copies you make implicitly: slices, sorted() returning a new list, string concatenation.
4. Memoization caches: one entry per state.

A useful trade-off framing: hash maps often buy time with space (Two Sum goes from O(n squared) time and O(1) space to O(n) time and O(n) space). Saying that trade-off out loud shows judgment. The guide to thinking out loud in coding interviews has phrasing for exactly these moments.

Complexity Mistakes That Cost Interview Points

These are the errors that show up most when candidates state complexity. Each one is easy to fix once you know to look for it.

The string point deserves extra attention. Hashing a string of length L costs O(L), so a hash map keyed by words of length L is O(L) per operation, not O(1). In problems like Group Anagrams, the honest complexity is O(n * L log L) when you sort each word as a key.

Finally, state complexity before the interviewer asks. Complexity analysis is typically graded as part of problem solving, not treated as an extra, as our breakdown of what interviewers look for in coding interviews explains. Offering it unprompted signals that you think about scale by default.

A Printable Big O Cheat Sheet Summary

If you print one block from this page, make it this one.

• O(1): array index, hash map get/set (avg), stack push/pop, deque ends, heap peek
• O(log n): binary search, balanced BST ops, heap push/pop, doubling or halving loops
• O(n): one pass, hash map counting, two pointers, sliding window, BFS/DFS (as O(V + E)), heapify, quickselect (avg)
• O(n log n): sorting, n heap operations, merge sort, Dijkstra (as O((V + E) log V))
• O(n^2): all pairs, naive nested loops, DP over two indices of the same array
• O(2^n): subsets, naive recursion with two branches
• O(n!): permutations