Complexity made visual
Big O Notation Explained
Big O notation describes how an algorithm's runtime or memory grows as the input size grows. This guide shows every complexity class from O(1) to O(2^n) on a live chart, with real numbers you can feel and sorting examples you already know.
TL;DR Big O in one answer
Big O gives you the shape of an algorithm's cost curve. O(1) is instant and constant.
O(log n) grows slowly. O(n) grows in a straight line. O(n log n)
grows a little faster and is where the best sorts live. O(n^2) grows like a square and is
where the simple sorts live. O(2^n) grows explosively and is unusable beyond small inputs.
Constants and micro-optimizations matter less than the curve, and the curve is what Big O names.
01The Big O growth chart
Six complexity classes plotted to n = 40 on a log scale. Notice how O(2^n) exits the top of the chart almost immediately while O(log n) barely rises.
Log-scaled y-axis. An O(1) algorithm costs the same whether there is one item or a billion.
02Every complexity class in plain English
| Class | Means | Example in sorting | Feels like |
|---|---|---|---|
O(1) |
Constant time, ignores input size | Swapping two elements | Instant |
O(log n) |
Halves the problem each step | Binary search on a sorted array | Nearly instant |
O(n) |
One pass over the data | Insertion Sort on sorted input | Linear and fast |
O(n log n) |
One pass, logged per step | Merge, Quick, Heap Sort | Fast, scales well |
O(n^2) |
Nested passes over the data | Bubble, Selection, Insertion Sort | Slow past 10,000 items |
O(2^n) |
Doubles for every added item | Brute-force subset problems | Impossible past ~30 items |
03What the numbers actually look like
Approximate operations for a single run at different input sizes. The gap between O(n log n) and O(n^2) is not linear, it is divide-and-conquer versus brute force.
| n | O(log n) | O(n) | O(n log n) | O(n^2) |
|---|---|---|---|---|
| 10 | 4 | 10 | 34 | 100 |
| 100 | 7 | 100 | 664 | 10,000 |
| 1,000 | 10 | 1,000 | 9,966 | 1,000,000 |
| 10,000 | 14 | 10,000 | 132,877 | 100,000,000 |
| 100,000 | 17 | 100,000 | 1.66 million | 10 billion |
| 1,000,000 | 20 | 1,000,000 | 19.9 million | 1 trillion |
04Big O of every sorting algorithm
Time complexity in the best, average, and worst cases, plus the extra memory each sort needs.
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Shell Sort | O(n log n) | O(n^1.25) | O(n^2) | O(1) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Yes |
05How to read Big O without fear
Look for the term that grows fastest and drop everything else. If your function does a loop of
n steps inside another loop of n steps, that is O(n^2) regardless of
the extra 2n work next to it. Drops the constants, keep the curve.
Two mistakes confuse beginners. First, big O does not tell you which algorithm is faster on small inputs; Insertion Sort beats Merge Sort below about 20 items even though its big O is worse. Second, space complexity is just as important as time; Merge Sort's O(n) buffer can be decisive on memory constrained devices, which is where in-place Heap Sort shines.
Count the dominant loop
A single pass over the data is O(n). A loop nested inside another loop is O(n^2). Recursion that halves the data is O(log n) per level.
Ask about memory
Does the algorithm build a second array (Merge Sort, O(n)) or rearrange in place (Heap Sort, O(1))? Note both when comparing.
Measure it for real
Open the Algorithm Race and watch measured comparisons and swaps line up with the theory on identical arrays.
06Frequently asked questions
QIs O(log n) faster than O(n)?
Yes, and the gap grows as n grows. Binary search on a billion items needs only about 30 steps, while a linear scan would need a billion. That is the difference between usable and unusable at scale.
QWhy do we ignore constants in Big O?
Because Big O answers the question of scaling, not of speed at one fixed size. Constants matter for fine tuning, but no constant can save O(n^2) at n equal to a million.
QWhat is the difference between best, average, and worst case?
Best case is the fastest input (often already sorted), worst case is the slowest (often reversed), and average case is the expected cost over typical inputs. Quick Sort is O(n log n) average but O(n^2) worst, while Merge and Heap Sort hold O(n log n) in all three.
QIs O(n log n) always better than O(n^2)?
Yes for large n, no for tiny n. Below a threshold around 20 items the constant overhead of divide and conquer makes straight Insertion Sort faster. Real libraries hybridize exactly this way, for example Timsort.
See the curve in action
The complexity chart comes alive when you watch algorithms race on real arrays.