Skip to content
Brute force first

Lesson 3.2

Count the steps

6 min · 7 steps

  1. Step 1 of 7 · Explanation

    One loop over n items takes about n steps. Two nested loops over the same items take about n × n steps. That's written O(n²).

    For 10 items the gap is small: 10 versus 100. For 100,000 items it's 100,000 versus 10,000,000,000. The bigger n gets, the faster n² pulls away from n.

  2. Step 2 of 7 · Predict the result

    What is steps at the end for n = 6?

    function solution(n) {  let steps = 0  for (let i = 0; i < n; i++) {    for (let j = 0; j < n; j++) {      steps++    }  }  return steps}
    1. 36
    2. 12
    3. 21
    4. 6

  3. Step 3 of 7 · Predict the result

    Two loops, but not nested. What does it return for n = 5?

    function solution(n) {  let steps = 0  for (let i = 0; i < n; i++) steps++  for (let j = 0; j < n; j++) steps++  return steps}
    1. 10
    2. 25
    3. 5

  4. Step 4 of 7 · Predict the result

    A loop that halves. What does it return for n = 64?

    function solution(n) {  let steps = 0  while (n > 1) {    n = Math.floor(n / 2)    steps++  }  return steps}
    1. 6
    2. 32
    3. 63

  5. Step 5 of 7 · Pick the approach

    n = 10⁵. You check every pair with j = i + 1, about 5 × 10⁹ checks. Assume a computer runs about 10⁸ simple steps per second, and the time limit is a few seconds.
    What happens?

    1. Too slow. About 50 seconds, so the test times out
    2. Fine, computers are very fast now
    3. Fine, because j = i + 1 already cuts the work

  6. Step 6 of 7 · Pick the approach

    Which one is O(n²)?

    1. A loop over nums, with nums.includes(x) inside it
    2. Two loops over nums, one after the other
    3. A while loop that halves n each round
    4. A loop over nums that reads nums[i - 1]

  7. Step 7 of 7 · Recap

    • Nested loops multiply, loops in sequence add.
    • Halving each round is O(log n), very few steps.
    • Watch for hidden loops like includes, indexOf and slice inside a loop.
    • A rough budget is about 10⁸ simple steps per second.

    Pattern card

    Count the steps
    When to use it: Before coding a brute force solution. Multiply the sizes of nested loops and compare with 10⁸.
    for ... for ...      // n × n  = O(n²)for ...; for ...     // n + n  = O(n)while (n > 1) n /= 2 // O(log n)