When loops nest: O(n squared)

Watch it run

CountPairs.java

1 / 30

Call countPairs([5, 9, 2, 7]) - a new frame is pushed onto the call stack.

step 1 / 30

Panels

Source

1int countPairs(int[] a) {

2 int count = 0;

3 for (int i = 0; i < a.length; i++) {

4 for (int j = i + 1; j < a.length; j++) {

5 count = count + 1;

6 }

7 }

8 return count;

10countPairs(new int[]{5, 9, 2, 7});

Data structures

No arrays or objects in scope yet -
primitives are shown in Variables.

Inspector

countPairs=ƒ countPairs

No primitive locals.

Execution log1 / 30

1CALLcountPairs([5, 9, 2, 7])L10

Legendcurrent linejust swapped / movedbeing comparedijpointers slide to the index they point atactive function framefilled DP cell

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: 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 the list - so for every item, it walks through the rest of the list again.

Press play and watch the inner counter. For a list of just 4 numbers, notice how many times 'count = count + 1' actually runs. It's not 4. It's not 8. The outer loop turns each of its steps into a whole lap of the inner loop.

Imagine it like this: At a party of n people where everyone must shake hands with everyone else. 4 people is manageable. 100 people is thousands of handshakes. The crowd doubled, but the handshakes quadrupled.

Words you just learned

nested loop: - a loop running inside another loop - the inner one restarts on every outer step

n times n is n squared

If the outer loop runs n times, and for each of those the inner loop runs about n times, then the total work is n multiplied by n - that's n squared. We write it O(n squared), and it is the danger zone of everyday code.

Why danger? Because squaring grows viciously. 10 items is 100 steps - fine. 1,000 items is 1,000,000 steps. 1,000,000 items is a trillion steps - your program appears to freeze. The input grew 1,000x but the work grew 1,000,000x. Nested loops over the same data are the single most common reason a beginner's code is mysteriously slow.

Remember these

One loop 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

Words you just learned

O(n squared): - quadratic time - work grows with the square of the input; watch for nested loops

Spotting it, and beating it

You don't need to count every step to smell O(n squared). Train your eye: whenever you see a loop over your data with another loop over the same data inside it, that's the shape. 'For every item, look at every other item' is the sentence that should make you pause.

The good news: many O(n squared) solutions can be rewritten to O(n) with a smarter data structure - a hash set, a sort, a single clever pass. That's a huge part of what the rest of this course teaches. But you can't fix a cost you can't see - which is exactly why we make it move on screen first.

Imagine it like this: Checking a class for duplicate names by comparing every student to every other student is O(n squared). Sorting the names first, then just scanning for neighbours that match, is far less work - the payoff of a better plan.

Check your understanding

0/3 answered

Q1A loop over n items, with another loop over the same n items inside it, is usually:

Q2You go from 1,000 items to 1,000,000 items (1,000x more) in an O(n squared) algorithm. The work grows by about:

Q3Which sentence is the warning sign of O(n squared)?