Guess the Big O
Read the snippet. Pick its time complexity before the bar runs out. Chain correct answers to multiply your score. 66 snippets in C++, Java, Python and Rust — or skip to the complexity cheat sheet.
High scores
Playing also counts toward your daily study time and streak.
Big O complexity cheat sheet
Big O notation describes how the work an algorithm does grows as its input grows. It drops constants and keeps only the dominant term, so 3n + 5 steps is simply O(n). The practice game above draws from 66 snippets covering all nine classes below.
| Complexity | Name | Doubling the input… | Typical example | Steps at n = 1,000 |
|---|---|---|---|---|
| O(1) | Constant | changes nothing | Hash table lookup, array index | 1 |
| O(log n) | Logarithmic | adds one step | Binary search, balanced tree lookup | ~10 |
| O(√n) | Root | multiplies by 1.41 | Trial division primality test | ~32 |
| O(n) | Linear | doubles the work | One loop over the input, linear search | 1,000 |
| O(n log n) | Linearithmic | slightly more than doubles | Merge sort, heap sort, most good sorts | ~10,000 |
| O(n²) | Quadratic | quadruples the work | Nested loops, bubble sort | 1,000,000 |
| O(n³) | Cubic | multiplies by 8 | Triple loop, naive matrix multiply | 1,000,000,000 |
| O(2ⁿ) | Exponential | squares the work | Recursive Fibonacci without memoisation | astronomical |
| O(n!) | Factorial | worse than squares it | Brute force permutations, naive TSP | astronomical |
Step counts are rough orders of magnitude, not exact operation counts. Anything below the O(n²) line stops being usable well before a million items.
How to work out time complexity
Most interview snippets give up their complexity to five rules. The game rewards recognising these on sight, because you only get ten seconds.
- Count loops over the input, not the work inside them. A loop body doing 50 arithmetic operations is still
O(n)— constants drop out. - Nested loops multiply; sequential loops add. Two nested loops over the same input are
O(n²). Two loops one after the other areO(n) + O(n) = O(n), because you keep the largest term. - Halving the range each step is
O(log n). Anything that discards half the remaining data per iteration — binary search, orwhile (n > 1) n /= 2— is logarithmic. - Divide and conquer that touches every element per level is
O(n log n). Merge sort splitslog ntimes and doesO(n)merging work at each level. - For recursion, think branches to the power of depth. Two recursive calls per step with depth
ngivesO(2ⁿ). Memoising collapses the repeated work, usually back toO(n).
The trap interviewers set most often: a loop that looks nested but isn't. Two pointers that each move forward at most n times total are O(n), not O(n²), even though one loop sits inside the other.
The complexity classes, explained
The same work regardless of input size. Constant does not mean fast — it means flat.
How hash tables reach O(1) →Throws away half the remaining work each step. A million items resolves in about 20 steps.
Binary search explained →Work grows in step with the input. One pass over an array or a linked list.
Array vs linked list →The practical floor for comparison sorting. Merge sort and heap sort live here.
Bubble sort vs merge sort →Every element compared against every other. Fine at n = 100, painful at n = 100,000.
Big O from scratch →Branching recursion that recomputes the same subproblems. The signal to reach for memoisation.
Dynamic programming →Frequently asked questions
What is Big O notation?
3n + 5 steps is written O(n). It is a statement about the shape of the growth curve, not about how many milliseconds something takes.Does O(1) mean instant?
O(1) means constant, not fast. An O(1) operation takes the same time no matter how large the input is, but that constant could still be slow. An O(1) hash lookup that computes an expensive hash can lose to an O(n) scan over ten items.Why do you drop constants and lower order terms?
n² term in n² + 500n is about two thousand times larger than the rest, so the smaller terms stop mattering.What is the difference between time and space complexity?
O(n²) scan into O(n) time at the cost of O(n) extra space. Full comparison →What is the difference between Big O, Big Theta and Big Omega?
How do I work out the complexity of a loop?
O(n). Nested loops multiply, so two nested loops over the same input are O(n²). Loops that halve the range each step are O(log n). Sequential loops add, and you keep the largest term.