Data Structures and Big-O Cheat Sheet for Coding Interviews

Data Structures and Big-O Cheat Sheet for Coding Interviews

Big-O describes how an algorithm's cost grows as its input grows. It does not describe how fast your code is.

That distinction is the whole subject. An interviewer asking "what's the complexity?" is asking whether your solution survives a thousand times more data — not whether it runs in eight milliseconds today.

This sheet covers the complexity ladder, the operation tables you look up, and the mapping from problem shape to data structure, which is the part that actually wins interviews.

Updated for 2026.

What Big-O Measures, and What It Ignores

Big-O is an upper bound on growth, with constants and lower-order terms deliberately thrown away.

Three things Big-O silently ignores, and all three cost you real milliseconds:

Constant factors. An O(n) algorithm with a huge constant loses to an O(n log n) one at every input size you will ever run.

Memory locality. Scanning a contiguous array is dramatically faster per element than following pointers through a linked list, because the CPU cache loads neighbours for free. Both are O(n).

Small inputs. Real sorting libraries fall back to insertion sort — an O(n²) algorithm — for subarrays of a few dozen elements, because its constants are tiny.

What people get wrong: treating Big-O as a benchmark. It is a filter for what scales, not a measurement of what is fast.

The Complexity Ladder

Every complexity you meet in an interview sits somewhere on this ladder. Learn one real example of each rather than the symbol.

The practical dividing line is O(n log n). Anything at or below it handles a million elements comfortably. Anything above it does not.

# O(1) — one operation regardless of size
value = my_dict[key]

# O(log n) — halves the search space each step
while lo <= hi:
    mid = (lo + hi) // 2

# O(n) — touches each element once
for x in arr: total += x

# O(n²) — every pair
for i in arr:
    for j in arr: check(i, j)

Each of these does the same abstract job — find or process data — and the loop structure alone tells you the class. Nested loops over the same input multiply; sequential loops add and then collapse to the larger term.

Rules for Reading Complexity Off Code

Sequential loops add, then collapse. O(n) + O(n) is O(2n) is O(n).

Nested loops multiply. A loop inside a loop over the same collection is O(n²).

Different inputs get different letters. Two nested loops over separate arrays is O(n·m), never O(n²).

Halving means log. Any loop that divides the remaining work by a constant factor each step is O(log n).

Recursion costs stack space. A depth-first search recursing n levels deep uses O(n) space even if it allocates nothing.

Complexity Table — Core Data Structures

Average case unless the worst case differs meaningfully, in which case both are shown.

* amortised — see the next section. k is the key length for a trie, not the number of stored keys.

The unbalanced BST row is the one people skip. A binary search tree built by inserting already-sorted data degenerates into a linked list, and every operation becomes O(n). Red-black trees and AVL trees exist entirely to prevent that, which is why std::map, Java's TreeMap, and most ordered maps are balanced trees rather than plain BSTs.

Graph Operations

Use an adjacency list by default. Interview graphs are almost always sparse, meaning E is far smaller than V², and the list wins on both memory and traversal. Use a matrix only when the graph is dense or you need constant-time edge lookups.

Sorting Algorithms

Quick sort's worst case is real but rare. It occurs when pivots are consistently terrible, such as always picking the first element of already-sorted input. Randomised or median-of-three pivot selection makes it vanish in practice, which is why quick sort remains the default in most standard libraries despite a worse worst case than merge sort.

Counting sort beats the O(n log n) barrier because it is not a comparison sort. It only works when values are integers in a bounded range k, and it costs O(k) memory — sorting a million values spread over a billion possible keys is a memory disaster.

Which Structure for Which Problem

This is the most useful table on the page. Most coding-interview problems are a lookup in it.

What people get wrong: reaching for a heap when a hash map is the answer, or sorting when a single hash pass would do. If a problem mentions "count", "seen", or "duplicate", the answer is almost always a hash structure.

Space Complexity

Space complexity counts memory that grows with input, not memory you happened to allocate.

The recursion stack counts. A recursive depth-first traversal allocates nothing explicitly and still uses O(h) space, where h is the height. On a degenerate tree that is O(n), and it is a genuine stack-overflow risk on large inputs.

Most O(n·m) DP tables collapse. If the recurrence only reads the previous row, keep two rows instead of the whole grid and the space drops to O(m). Interviewers love this follow-up.

Amortised vs Worst Case

Two structures on this page have a worst case that almost never happens, and you must be able to explain both.

Dynamic array resize

arr = []
for i in range(n):
    arr.append(i)   # usually O(1) — occasionally O(n)

When the backing buffer fills, the array allocates a larger one (typically double) and copies everything across — an O(n) operation. Because capacity doubles, that copy happens after 1, 2, 4, 8, 16… appends. Summing the copy costs across n appends gives roughly 2n total work, so the amortised cost per append is O(1).

Say it as: amortised O(1), worst case O(n) on the resize.

Hash collisions

A hash map is O(1) because a good hash function spreads keys across buckets evenly. If every key lands in the same bucket, lookup degenerates to scanning a list — O(n).

This is not purely theoretical. It is the basis of hash-flooding denial-of-service attacks, which is why modern runtimes randomise hash seeds per process. Java additionally converts long collision chains into balanced trees, capping the worst case at O(log n) rather than O(n).

Say it as: O(1) average, O(n) worst case with pathological collisions.

How to State Your Complexity in an Interview

Do not announce a symbol. Justify it in one sentence, and always give time and space separately.

Weak: "It's O(n)."

Strong: "Time is O(n log n) — we sort once, then make a single linear pass. Space is O(n) for the hash map, plus O(log n) for the sort's recursion stack."

Three habits that separate strong candidates:

Define your variables. In a graph problem there is no single n. Say O(V + E). In a problem with n strings of length k, say O(n · k) — not O(n).

State the worst case when it differs. "Average O(1), worst O(n) if every key collides" shows you know why the structure works.

Name the tradeoff you chose. "I used O(n) extra space to get time down from O(n²) to O(n)" is the sentence that turns a correct answer into a good one.

The Five Mistakes

1. Treating Big-O as a speed measurement. It measures growth. An O(n log n) algorithm regularly beats an O(n) one on real inputs because of constants and cache behaviour. Use Big-O to rule out what cannot scale, then profile.

2. Forgetting recursion stack space. Claiming O(1) space for a recursive solution is wrong. The stack grows with depth, and on a skewed structure that is O(n).

3. Calling hash map lookup unconditionally O(1). It is O(1) average, O(n) worst case. The complete answer takes four extra words and demonstrably separates candidates.

4. Using O(n²) for two nested loops over different inputs. Two separate collections give O(n · m). Collapsing them to n² hides the fact that one input may be tiny.

5. Sorting when a hash pass would do. Sorting costs O(n log n). If you only need membership, counting, or complements, a hash structure gets you O(n). Reaching for sort() first is the most common avoidable complexity in interview answers.

Print This Section

LADDER   O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
         practical cutoff for 1M items: O(n log n)

READ     sequential loops  → add, then keep the larger
         nested loops      → multiply
         halving each step → log n
         two inputs        → O(n·m), never O(n²)

PICK     seen it before / count it   → hash set / hash map
         last in first out           → stack
         level by level              → queue (BFS)
         top K / running extreme     → heap
         sorted + frequent inserts   → balanced BST
         prefix on strings           → trie
         merge groups                → union-find
         contiguous sub-range        → sliding window

CAVEAT   dynamic array append  amortised O(1), worst O(n)
         hash map lookup       average O(1), worst O(n)
         unbalanced BST        O(log n) hoped, O(n) real

SAY IT   "Time O(x) because <one reason>. Space O(y) including recursion."

Complexity is the language interviewers use to ask whether your solution survives growth. Learn the ladder and the structure-to-problem mapping, and most of the rest is arithmetic you can do out loud.

🔗 Next in this collection: 15 Coding Interview Patterns That Solve Most Problems, or return to The Complete Developer Cheat Sheet Collection.