Why we don't measure in seconds
Say two friends each look for one name in a phone book. Aria flips page by page from the front. Bex opens to the middle, decides which half the name is in, and repeats on that half. On a thin book they finish about the same time. On a
10,000-page book, Aria is still flipping while Bex is already done.The thing that made Bex win isn't a faster finger — it's a smarter method. What we actually care about is how the work grows as the input gets bigger, and that's exactly what time complexity measures. Not "how many seconds" (that changes with your laptop, the weather, what else is running) — but how does the effort scale as the input grows.
We write it with a capital O:
- if the work grows in step with the input size
n, we writeO(n)— double the input, double the work - if the work barely grows at all, no matter how big
ngets, that'sO(1)— constant
Read
O(n) out loud as "oh of n." That's the whole mindset: forget the clock, ask how does the pile of work grow as n grows?Counting steps, not clocks
So how do we actually get an
O(...)? We count the basic steps the code takes, written as a function of the input size n (n just means "how big the input is" — the length of the list, the number of items).Take the simplest job: look at every item in a list once. If the list has
n items, that's n steps — one glance per item. We don't care that each glance takes a few nanoseconds; we care that the count is n. Count it for a few sizes and the pattern is obvious:| List size n | Steps taken |
|---|---|
| 4 | 4 |
| 10 | 10 |
| 1,000 | 1,000 |
The steps track
n exactly, so this is linear time, O(n). Here it is counted in code — the function returns how many steps it took:function stepsLinear(list) {
let steps = 0;
for (const item of list) {
steps++; // one step per item
}
return steps;
}
console.log(stepsLinear([5, 2, 9, 1])); // 4Quick check
A loop reads each of n items exactly once. If you double n, the step count…
Answer it in the interactive lesson to keep your progress.
The five you'll actually meet
Almost every algorithm you'll see lands in one of five buckets. From cheapest to most expensive:
O(1)constant — the work is the same no matter how bignis. Readingarr[i]by index isO(1).O(log n)logarithmic — you halve the problem each step, so it grows very slowly. Binary search.O(n)linear — one pass over the input. A single loop.O(n log n)linearithmic — the good sorts. A hair above linear.O(n²)quadratic — a loop inside a loop; you touch every pair. Explodes fast.
Why the ranking matters — here's how many steps each takes as
n grows to a million:| n | O(1) | O(log n) | O(n) | O(n²) |
|---|---|---|---|---|
| 8 | 1 | 3 | 8 | 64 |
| 1,000 | 1 | 10 | 1,000 | 1,000,000 |
| 1,000,000 | 1 | 20 | 1,000,000 | 1,000,000,000,000 |
Look at the last row:
O(1) and O(log n) stay tiny, O(n) is manageable, and O(n²) has become a trillion. That gap is why we obsess over complexity.Quick check
Which of these grows the SLOWEST as n gets huge?
Answer it in the interactive lesson to keep your progress.
O(log n): the power of halving
O(log n) feels almost magical, so it's worth seeing where it comes from. Whenever each step lets you throw away half of what's left, the count is log₂(n) — "how many times can I halve n before I reach 1?"Halving
16: 16 → 8 → 4 → 2 → 1 — that's 4 halvings. Halving 1,000,000 reaches 1 in only about 20 steps. That's the whole reason binary search is so fast. Count the halvings directly and watch how slowly it grows:| n | Halvings until 1 (log₂ n) |
|---|---|
| 16 | 4 |
| 32 | 5 |
| 1,024 | 10 |
| 1,048,576 | 20 |
The count barely moves even as
n rockets upward — that's logarithmic growth. (You'll use this directly in the Binary Search lesson later — no need to know it yet.)function stepsHalving(n) {
let steps = 0;
while (n > 1) {
n = Math.floor(n / 2); // throw away half
steps++;
}
return steps;
}
console.log(stepsHalving(16)); // 4Quick check
You can halve a problem each step. For n = 1,024, roughly how many steps?
Answer it in the interactive lesson to keep your progress.
O(n²): why a loop inside a loop is dangerous
The one to watch out for is
O(n²). It shows up whenever you compare every item with every other item — a loop nested inside another loop over the same data.Imagine checking every pair of people in a room to see who knows whom. With
n people, the number of pairs is about n × n — the work grows with the square of the input:| People n | Pairs to check |
|---|---|
| 4 | 6 |
| 10 | 45 |
| 100 | 4,950 |
| 1,000 | 499,500 |
Ten people is nothing, but a thousand people is already half a million checks — and a million people would be five hundred billion. A hidden
O(n²) is the most common reason a solution that "worked on the small example" grinds to a halt on real data. The fix is usually to replace the inner loop with something cheaper — a sorted scan (O(n log n)) or a hash-map lookup (O(n)), which you'll meet in later lessons.Quick check
A loop inside a loop, each running over all n items, is usually…
Answer it in the interactive lesson to keep your progress.
Space complexity: memory grows too
Time isn't the only cost. Space complexity measures how much extra memory an algorithm needs as
n grows — same idea, same notation.O(1)space — you use a fixed handful of variables no matter how big the input is (a running total, two pointers). This is the cheap, ideal case.O(n)space — you build a new structure that grows with the input (a copy of the list, a hash map of everything you've seen).
There's often a trade-off: spending
O(n) memory can buy you faster time. For example, remembering values you've already seen (costing O(n) space) can turn an O(n²) double-loop into a single O(n) pass. Knowing both costs lets you make that call on purpose.Quick check
An algorithm that only ever keeps a couple of variables (like a running total) uses…
Answer it in the interactive lesson to keep your progress.
Reading it out loud — and what's next
Two habits make Big-O easy to read:
- Drop the constants.
O(2n)andO(n + 5)are both justO(n)— we only care about the shape of the growth, not the exact count. - Keep only the biggest term.
O(n² + n)isO(n²), because for largenthen²part dwarfs everything else.
We can even write the exact step count as a formula and then simplify it. Checking every pair of
n items takes which multiplies out to (n² − n) / 2. Drop the constant ½ and the smaller n, and what's left is the shape: O(n²).Key takeaways:
- Complexity counts how work grows with n, not seconds — so it's fair across machines.
- The ladder, cheapest first:
O(1)<O(log n)<O(n)<O(n log n)<O(n²). - Halving each step →
O(log n); one pass →O(n); every pair →O(n²). - Space counts extra memory the same way; time and space often trade off.
From here on, every topic tags its operations with this notation — "access is
O(1)," "search is O(n)," "a good sort is O(n log n)." You now speak the language the whole course is written in. Next up: Arrays, where O(1) index access is the superpower everything builds on.