Almost every coding interview ends with the same question: "What's the time and space complexity?" This Big-O cheat sheet is the reference you want open while you study — the complexity classes that matter, and clean tables for the data structures, sorting algorithms, and patterns that show up again and again. Bookmark it, drill it, and the complexity answer becomes automatic.
If you want to recognize which algorithm to reach for in the first place, pair this with our 15 LeetCode patterns guide and dynamic programming patterns. Big-O tells you how fast your solution is; the patterns tell you what to write.
What Big-O Actually Means
Big-O describes how an algorithm's running time (or memory) grows as the input size grows. It drops constants and lower-order terms, so 3n + 50 and n/2 are both just O(n). The point isn't a stopwatch number — it's the shape of growth. Double the input and an O(n) routine roughly doubles; an O(n²) routine quadruples.
By convention Big-O reports the worst case unless you say otherwise. Constants still matter in real life, but at interview scale the class is what your interviewer is scoring.
The Complexity Classes
From fastest-growing-slowest to flat-out-explosive, here are the classes you will actually be asked about, with a plain-English meaning and a concrete example.
| Notation | Name | Plain-English meaning | Example |
|---|---|---|---|
O(1) | Constant | Same work no matter the input size. | Hash-map lookup; array index access. |
O(log n) | Logarithmic | Halve the problem each step. | Binary search in a sorted array. |
O(n) | Linear | Touch every element once. | Scanning an array to find the max. |
O(n log n) | Linearithmic | A linear pass that does log-work each step. | Efficient sorting (mergesort, heapsort). |
O(n²) | Quadratic | A loop inside a loop over the input. | Comparing every pair (naive duplicate check). |
O(2ⁿ) | Exponential | Work doubles with each added element. | Generating every subset; naive recursive Fibonacci. |
O(n!) | Factorial | Try every possible ordering. | Brute-force permutations; naive travelling salesman. |
n ≤ 20 tolerates O(2ⁿ); n ≤ 5000 tolerates O(n²); n ≤ 10⁶ needs O(n log n) or better; n ≤ 10¹⁸ demands O(log n).
Data Structure Operations
The single most common follow-up is "what's the complexity of inserting / searching / deleting here?" These are the average-case figures; where the worst case differs sharply it's noted in the row.
| Data structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array (static) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Dynamic array | O(1) | O(n) | O(1) amortized* | O(n) | O(n) |
| Hash map / hash set | — | O(1) avg, O(n) worst | O(1) avg, O(n) worst | O(1) avg, O(n) worst | O(n) |
| Stack | O(n) | O(n) | O(1) push | O(1) pop | O(n) |
| Queue | O(n) | O(n) | O(1) enqueue | O(1) dequeue | O(n) |
| Singly linked list | O(n) | O(n) | O(1) at head | O(1) at head | O(n) |
| Binary heap | O(1) peek | O(n) | O(log n) | O(log n) | O(n) |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
*Dynamic-array append is O(1) amortized: the occasional O(n) resize is spread across many cheap appends. Inserting in the middle is still O(n) because of the shift.
Sorting Algorithm Complexities
Know these cold — sorting comes up constantly, and the gap between the average and worst case for quicksort is a favorite interviewer trap.
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Counting / radix sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes |
Counting and radix sort beat the O(n log n) comparison-sort lower bound because they don't compare elements — they bucket by value, where k is the value range or digit count. They only pay off when k is small relative to n.
Common Pattern Complexities
Most interview solutions are built from a handful of patterns, and each carries a recognizable complexity. State it the moment you pick the pattern.
| Pattern | Time | Space | Why |
|---|---|---|---|
| Two pointers | O(n) | O(1) | Single pass with two indices, no extra structure. |
| Sliding window | O(n) | O(k) | Each element enters and leaves the window once; state holds up to k items. |
| BFS / DFS (graph) | O(V + E) | O(V) | Visit every vertex and edge once; store visited set / recursion stack. |
| Binary search | O(log n) | O(1) | Halve the search space each step. |
| Heap top-K | O(n log k) | O(k) | n pushes/pops on a heap capped at size k. |
| Dynamic programming | O(states × transition) | O(states) | Each subproblem solved once; memo holds one entry per state. |
| Backtracking | O(2ⁿ) or O(n!) | O(n) | Explores the full decision tree; depth-n recursion stack. |
DP complexity is mechanical once you frame it: number of distinct states × cost per transition. A 1D DP over an array with O(1) transitions is O(n) time, O(n) space — and often O(1) space if you only keep the last few rows. See the DP patterns guide for the full breakdown.
How to Analyze Complexity Out Loud
Interviewers don't just want the answer — they want to hear you derive it. A repeatable script:
- Name the input size. "Let n be the length of the array, m the number of queries." Define every variable before you use it.
- Count the dominant loop. One pass is O(n). A nested loop over the same input is O(n²). A loop that halves each step is O(log n).
- Account for hidden work. A
.sort()is O(n log n). A set membership check is O(1). Slicing a list is O(n), not free. - Add, then drop the small terms. "Sorting is O(n log n), then one linear pass is O(n), so overall O(n log n)." Keep only the biggest term.
- Do space separately. Count auxiliary memory: the recursion stack, the hash map, the output array. Call out when your solution is O(1) extra space — that's a strong signal.
- State worst vs. average if they differ. "Average O(1) for the hash lookups, but O(n) worst case under heavy collisions."
Practicing this out loud is exactly what separates a candidate who knows Big-O from one who can communicate it. For the structured approach to the whole answer, see how to answer coding interview questions.
Get real-time complexity analysis in your interview
CoPilot Interview's coding copilot reads the problem on your screen and gives you a clean solution with the full time and space complexity worked out — so you can explain the Big-O confidently instead of guessing.
Try the Coding Copilot Free →FAQ
What is Big-O notation in simple terms?
Big-O describes how the running time or memory of an algorithm grows as the input gets larger. It ignores constants and lower-order terms, so it captures the shape of growth rather than an exact stopwatch time. O(n) means work grows linearly with input size; O(n²) means it grows with the square of the input.
Should I quote best, average, or worst case in an interview?
State the worst case by default — that's what Big-O conventionally measures and what interviewers expect. Mention the average case when it differs meaningfully (for example, quicksort is O(n log n) average but O(n²) worst, and hash map lookups are O(1) average but O(n) worst).
Is O(1) always faster than O(n)?
For large inputs, yes — O(1) does constant work regardless of size. But for small inputs a high-constant O(1) or O(log n) operation can be slower than a low-constant O(n) scan. Big-O describes growth, not absolute speed, so it only guarantees the faster class once the input is large enough.
What is amortized complexity?
Amortized complexity is the average cost per operation across a long sequence of operations. A dynamic array append is O(1) amortized: most appends are O(1), and the occasional O(n) resize is spread across the many cheap appends that follow it.
Do I need to analyze space complexity too?
Yes. Interviewers increasingly ask for both. Space complexity counts the extra memory your algorithm allocates beyond the input — recursion stack frames, auxiliary arrays, hash maps, and so on. Saying an in-place solution is O(1) space is often a strong signal.