O(n²)

JavaScript · Unit 21: Complexity

Full plan
JavaScript
8 exercises

A loop inside another loop changes everything: the inner one runs all the way through on every turn of the outer one.

With n = 5 that is 25 steps; with n = 10, a hundred. That is O(n²), "order n squared".

function steps(n) {
  let s = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      s++;
    }
  }
  return s;
}
console.log(steps(5), steps(10));

Prints

25 100

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

1. Predict the output
If n goes from 10 to 20, what happens to the counter?
2. Complete the code
Complete it to count each pair once (and never pair an item with itself).
3. Predict the output
This one counts pairs, not full turns. What does it print?
4. Multiple choice
An O(n²) program does a million steps with 1000 items. How many does it do with 10,000?
5. Find the bug
It should print every pair in the array (1-2, 1-3 and 2-3). Which line has the error?
6. Put the lines in order
Build the counter for a loop inside another loop.
7. Predict the output
Here the two loops walk over different arrays. What does it print?
8. Predict the output
Two counters in the same program, one outside and one inside. What does it print?

Do this lesson

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.

See all lessons →