Big O Cheat Sheet for Coding Interviews: Time and Space Complexity Explained

Almost every coding interview ends with the same question: "What's the time and space complexity of your solution?" A correct answer, explained clearly, is an easy way to earn points. A shaky one can undo a good solution.

This cheat sheet covers what you need to know, and how to explain it out loud.

What Big O measures

Big O describes how the running time or memory use grows as the input grows. It ignores constants and lower-order terms, because for large inputs the dominant term is what matters. A loop that does 3n + 10 operations is simply O(n).

In interviews, "complexity" usually means the worst case, unless you say otherwise. If average and worst case differ (like hash tables or quicksort), mention both.

Common complexity classes

From fastest to slowest:

Big O	Name	Typical example
O(1)	Constant	Array index, hash map lookup (average)
O(log n)	Logarithmic	Binary search, balanced BST operations
O(n)	Linear	Single pass over an array
O(n log n)	Linearithmic	Efficient sorting (merge sort, heap sort)
O(n²)	Quadratic	Nested loops over the same input
O(2ⁿ)	Exponential	Generating all subsets
O(n!)	Factorial	Generating all permutations

A useful rule of thumb for constraints: if n is up to about 10⁵ or 10⁶, the interviewer probably expects O(n) or O(n log n). If n is around 20, exponential solutions may be acceptable.

Data structure operations

Structure	Access	Search	Insert	Delete
Array	O(1)	O(n)	O(n)	O(n)
Dynamic array (append)	O(1)	O(n)	O(1) amortized at end	O(n)
Linked list	O(n)	O(n)	O(1) with a pointer	O(1) with a pointer
Hash map / set	n/a	O(1) average, O(n) worst	O(1) average	O(1) average
Balanced BST	O(log n)	O(log n)	O(log n)	O(log n)
Binary heap	O(1) peek	O(n)	O(log n)	O(log n) pop
Stack / queue	O(1) top	O(n)	O(1)	O(1)
Trie	n/a	O(k) for a key of length k	O(k)	O(k)

Algorithm costs

Algorithm	Time	Space
Binary search	O(log n)	O(1) iterative
Merge sort	O(n log n)	O(n)
Quicksort	O(n log n) average, O(n²) worst	O(log n) stack
Heap sort	O(n log n)	O(1)
Counting sort	O(n + k)	O(k)
BFS / DFS on a graph	O(V + E)	O(V)
Dijkstra with a heap	O((V + E) log V)	O(V)
Topological sort	O(V + E)	O(V)
Union-find (with optimizations)	Nearly O(1) per operation	O(n)

How to analyze your own code

Work through your solution in this order:

1. Loops. A loop over n items is O(n). A nested loop over the same items is O(n²). Loops one after another add up: O(n) + O(n) is still O(n).
2. Halving. If each step cuts the problem in half, that's O(log n).
3. Recursion. Multiply the number of calls by the work per call. A recursive function that branches twice with depth n makes about 2ⁿ calls.
4. Library calls. Sorting is O(n log n). Slicing or copying a list is O(n). String concatenation in a loop can secretly be O(n²) in some languages.
5. Space. Count extra data structures you create, plus the recursion stack. The input itself usually doesn't count.

Watch for hidden costs

• in on a list is O(n), but on a set or dict it's O(1) on average.
• Removing from the front of an array is O(n). Use a deque instead.
• Building strings with += inside a loop can be quadratic. Collect parts and join once.
• Recursion depth uses stack space even when you allocate nothing else.

Amortized complexity

Some operations are usually cheap but occasionally expensive. Appending to a dynamic array is the classic example: most appends are O(1), but when the array grows it copies everything. Averaged across many appends, the cost is still O(1) amortized. Say "amortized" when you use it, so the interviewer knows you understand the difference.

How to explain complexity out loud

Interviewers care about your reasoning as much as the final answer. A clear explanation sounds like this:

"We sort the intervals first, which is O(n log n). Then we do a single pass to merge them, which is O(n). Sorting dominates, so the total time is O(n log n). For space, the output list can hold up to n intervals, so that's O(n), plus whatever the sort uses internally."

Name each step, give its cost, and say which one dominates. If you can, mention a trade-off: "We could avoid the extra space by merging in place, at the cost of mutating the input."

Use complexity to guide your approach

Complexity isn't only something to state at the end. Use it at the start:

• Brute force first. State the naive solution and its complexity, then ask how to improve it.
• Look for repeated work. Recomputing the same thing points to memoization or a prefix sum.
• Trade space for time. A hash map often turns O(n²) into O(n).
• Spot the pattern. Many problems map onto a known technique with a known cost. Our guide to 12 coding interview patterns pairs each pattern with its typical complexity.

Keep this cheat sheet nearby as you practice, and get in the habit of stating complexity for every problem you solve. After a few weeks, you'll analyze new code without thinking about it.