Unit 5 · Data and algorithms
Why nested loops get slow: O(n²) by feel
Two loops one after the other add their work. A loop inside a loop multiplies it: for each of n items, the inner loop runs n times, which is n × n. Ten thousand items means 100 million steps.
The mix-up
What people often think
“Two loops means twice the work.”
What the tutor says
A loop inside a loop multiplies. For each of n items, the inner loop runs n times: n × n steps.
With 1,000 items, how many times does compare run?
How it works
A test with 10 items hides the shape of the curve: 100 steps is instant. Grow the data ten times and an n² algorithm does a hundred times the work.
The code is not buggy; it gives the right answer. It just does far too much work. A faster server only halves the time, while a better algorithm, often a lookup in an object instead of an inner loop, can cut it from n² to n.
An example
for (const a of items) { // n times
for (const b of items) { // n times each
compare(a, b); // n × n in total
}
}Close cousins of this mix-up
The tutor watches for these in the same lesson.
“If it is fast on my laptop, it is fast.”
A test with 10 items hides the shape of the curve. At 10,000 items, n² means 100 million steps.
“Faster hardware fixes slow code.”
A server twice as fast only halves 10 billion steps. Changing the algorithm from n² to n cuts it to 100,000.
“If it slows down, there must be a bug.”
The code is correct; it gives the right answer. It is just doing far too much work as the list grows.
Practise it with a tutor watching
Big O by feel
Look at a piece of code and say roughly how its work grows as the data grows.
Free, no account needed.