When loops nest: O(n squared)

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.

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.

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.

How to spot quadratic code in the wild

Nested loops are easy to see when they are written as two for statements. In real code they hide, and learning the disguises is what makes this lesson practical.

The most common disguise is a method call inside a loop. list.contains(x) looks like one step and walks the entire list; string.indexOf(y) does the same. A loop containing either is quadratic even though only one loop is visible.

The second disguise is string concatenation in a loop. Strings are immutable, so s += x builds a brand new string each time, copying everything accumulated so far. A thousand appends copies roughly half a million characters.

The third is repeated sorting or searching inside a loop - sorting inside a loop over n items is n times n log n, which is worse than quadratic.

// looks linear, is quadratic - contains() walks the whole list
for (String name : names) {
    if (seen.contains(name)) duplicates.add(name);   // O(n) inside O(n)
    seen.add(name);
}

// looks linear, is quadratic - each += copies the whole string
String out = "";
for (String part : parts) out += part;

// the fixes
Set<String> seenFast = new HashSet<>();      // contains() is now O(1)
StringBuilder sb = new StringBuilder();      // append() does not copy

10,000 items

list.contains in a loop     ~50,000,000 comparisons    ~380 ms
set.contains in a loop           ~10,000 lookups         ~2 ms

string += in a loop         ~50,000,000 chars copied   ~410 ms
StringBuilder.append             ~10,000 appends         ~1 ms

Recap

A loop inside a loop multiplies: n outer passes times n inner steps is n squared, and doubling the input quadruples the work.

That is survivable at small sizes and impossible at large ones, and the crossover arrives faster than people expect - a million items is a trillion steps.

The skill this lesson builds is not spotting two for statements. It is noticing the loop you did not write, hiding inside a method call on the line in front of you.