Call countPairs([5, 9, 2, 7]) - a new frame is pushed onto the call stack.
primitives are shown in Variables.
Real execution, step by step. Press play or scrub with the controls - every variable and array index updates live.
A loop inside a loop
Last lesson, one loop walked through the list once - a fair O(n). Now watch what happens when we put a loop inside another loop. The method above counts how many pairs of items exist in a list, so for every item it walks through the rest of the list again. One outer step becomes a whole lap of the inner loop.
Press play and keep your eye on the line 'count = count + 1'. For a list of just four numbers, count how many times it actually runs. It isn't 4. It isn't 8. It's 6 - and the reason it grows so fast is the whole point of this lesson.
Every time the outer loop takes one step, the inner loop runs from scratch. So the total number of inner steps is roughly the list size, multiplied by itself. That multiplication is where the trouble hides.
Imagine it like this: A party of n people where everyone must shake hands with everyone else. 4 people is a handful of handshakes. 100 people is thousands. The crowd grew 25 times, but the handshakes grew over 600 times.
- nested loop
- - a loop running inside another loop - the inner one restarts on every outer step
Why squaring is so vicious
If the outer loop runs n times and the inner loop runs about n times for each, the total work is n multiplied by n: n squared. We write it O(n squared), read 'order n squared', and it is the danger zone of everyday code.
Here is why it deserves that name. Compare it to the honest O(n) from last lesson, side by side, and watch what happens as the list grows. The two costs start close and then rip apart.
At just 1,000 items, an O(n) pass does 1,000 steps while O(n squared) does a million. Grow the list to a million items and O(n squared) becomes a trillion steps - a program that appears to freeze. Same input, a million times the pain.
- One pass over n: about n steps - O(n)
- A loop inside a loop over n: about n squared steps - O(n squared)
- Squaring is brutal: 1,000x more data means 1,000,000x more work
- O(n squared)
- - quadratic time - work grows with the square of the input; the mark of nested loops
Spotting it, and beating it
You don't need to count every step to smell O(n squared). Train your eye on one shape: a loop over your data, with another loop over the same data inside it. The sentence 'for every item, look at every other item' should make you pause every single time.
The good news, and the promise of this whole course: most O(n squared) solutions can be rewritten to O(n) with a smarter tool - a hash set, a sort, a single clever pass. You can't fix a cost you can't see, though, which is exactly why we make it move on screen first.
Imagine it like this: Finding duplicate names by comparing every student to every other student is O(n squared). Sorting the names first, then scanning for matching neighbours, is far less work - the payoff of a better plan.
Two loops over the same array is the classic O(n squared). Two loops over different arrays (size n and size m) is only O(n times m) - often fine. The danger is looping over the same data twice.