How much slower does a program get when you give it more to do? See the curves, read the code, and find out.
Big O is a way to describe how much slower a computer program gets when you give it more stuff to work on. The letter n means “how many items there are.” So O(n) means the work grows at the same rate as the number of items, and O(n²) means it grows like n × n.
Big O doesn't care about exact seconds. It only cares about the shape of the growth. When n gets big, the shape is what matters most.
Try it: click the buttons below to add curves to the graph. Hover over the graph to see the numbers, and read the code to see what each one looks like in a real program.
Quadratic: a loop inside a loop. Double the input and you get 4 times the work. Like every kid in class shaking hands with every other kid.
// O(n²) — bubble sort
function bubbleSort(arr: number[]): number[] {
const a = [...arr];
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
[a[j], a[j + 1]] = [a[j + 1], a[j]];
}
}
}
return a;
}
// Two nested loops: every pair of elements
// is compared. n=1000 → ~500,000 comparisons.Say a program can handle n = 10 items in one second. If we got a computer 1,000 times faster, how many items could it handle in that same second? Notice how a super-fast computer barely helps the slow ones at the bottom.
| Big O | Steps at n=10 | 1,000× faster computer | 1,000,000× faster computer |
|---|---|---|---|
| O(1) | 1 | ∞ | ∞ |
| O(log n) | 3 | ∞ | ∞ |
| O(n) | 10 | 10k | 10.0M |
| O(n log n) | 33 | 3k | 1.6M |
| O(n²) | 100 | 316 | 10k |
| O(n³) | 1.0k | 100 | 1k |
| O(2ⁿ) | 1.0k | 20 | 30 |
| O(n!) | 3.6M | 12 | 15 |