Algorithms from zero

Counting the steps

Crux The cost of an algorithm is how many basic operations it performs. Count the steps for a given input size n, and see how the count grows as n grows.

◷ 18 min

Suppose you write two algorithms to solve the same problem. One visits every element in a list once. The other visits every pair of elements. For a list of 100 items, the first does 100 steps, the second does 10,000. How did we know this? We counted the steps. This is how you measure an algorithm’s cost before you ever run it.

Goal

After this lesson you can count the number of basic steps an algorithm performs as a function of input size n, predict how that count grows (linear, quadratic, and so on), and see why the growth rate matters more than the exact number.

The idea

A basic operation is a step the computer does in constant time: assignment, comparison, arithmetic, array access. Every algorithm is built from many basic operations. The step count of an algorithm is how many basic operations it performs on a given input.

The key insight: the step count depends on the size of the input. For the largestOf function (from lesson 01), the input is a list of n numbers. The step count is roughly n − 1 (one comparison per element after the first). For a different algorithm that checks every pair of elements, the step count is roughly n × n.

Let us count the steps for largestOf:


      1
      function largestOf(numbers) {
    

      2
      let largest = numbers[0];           // 1 step
    

      3
      for (let i = 1; i < numbers.length; i++) {
    

      4
        if (numbers[i] > largest) {       // 1 comparison per loop
    

      5
          largest = numbers[i];           // 1 assignment (sometimes)
    

      6
        }
    

      7
      }
    

      8
      return largest;                     // 1 step
    

      9
      }

L1 Setup: 1 assignment
L2 Loop runs n-1 times. Each iteration does 1 comparison + maybe 1 assignment
L6 Return: 1 step

Inside the loop, the critical operation is the comparison numbers[i] > largest. This happens exactly n − 1 times (once for each element after the first). So the step count is about n − 1.

Now consider a different algorithm: count how many pairs of equal numbers are in a list. To check every pair, you need nested loops:

function countEqualPairs(numbers) {
  let count = 0;
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) {
        count++;
      }
    }
  }
  return count;
}

The outer loop runs n times. The inner loop runs roughly n times (on average). So the total is roughly n × n = n² comparisons. For a list of 100 items, this is 10,000 comparisons. For a list of 1,000 items, this is 1,000,000 comparisons.

The step count is a function of n. We write:

largestOf has a step count of roughly n − 1.
countEqualPairs has a step count of roughly n².

What matters is how the step count grows as n grows. If you double n, the step count for largestOf roughly doubles. If you double n for countEqualPairs, the step count roughly quadruples (because n² grows much faster than n).

The code

Let us implement both algorithms and count the steps by hand.

Algorithm 1: Find the largest number

function largestOf(numbers) {
  let largest = numbers[0];
  for (let i = 1; i < numbers.length; i++) {
    if (numbers[i] > largest) {
      largest = numbers[i];
    }
  }
  return largest;
}

Algorithm 2: Count equal pairs

function countEqualPairs(numbers) {
  let count = 0;
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) {
        count++;
      }
    }
  }
  return count;
}

Try both on a small list:

Output

Both work, but notice: largestOf is fast even on large lists. countEqualPairs grows much slower as the list size increases.

Step-by-step trace

Let us trace countEqualPairs on a small list [3, 9, 3] and count the comparisons:


      1
      function countEqualPairs(numbers) {
    

      2
        let count = 0;
    

      3
        for (let i = 0; i < numbers.length; i++) {
    

      4
          for (let j = i + 1; j < numbers.length; j++) {
    

      5
            if (numbers[i] === numbers[j]) {
    

      6
              count++;
    

      7
            }
    

      8
          }
    

      9
        }
    

      10
        return count;
    

      11
      }

For n = 3, we did 3 comparisons. For n = 4, we would do 6 comparisons (1 + 2 + 3). For n = 5, we would do 10 comparisons (1 + 2 + 3 + 4). The pattern is n × (n − 1) / 2, which is roughly n².

Complexity

Now let us think about growth. Suppose we know the step count as a function of n:

largestOf: step count ≈ n − 1
countEqualPairs: step count ≈ n × (n − 1) / 2, which is roughly n²

What happens when n doubles?

Input size n	largestOf steps	countEqualPairs steps
10	9	45
20	19	190
100	99	4,950
200	199	19,900

Notice: when n goes from 10 to 100, largestOf steps go from 9 to 99 (10× increase). But countEqualPairs steps go from 45 to 4,950 (110× increase). Quadratic growth is much worse than linear growth.

Why does this matter? As the input gets larger, an algorithm with quadratic step count becomes impractical much faster than one with linear step count. For processing a million items, linear takes 1 million steps; quadratic takes 1 trillion steps.

The dominant term is what matters most. For countEqualPairs, the n² term dominates; the linear and constant terms are negligible. For largestOf, the n term dominates.

We care about how the step count grows in proportion to n, not the exact number of steps.

Practice 0 / 5

How many comparisons does largestOf perform on a list of 50 items?

For countEqualPairs on a list of 4 items, how many comparisons? (Hint: 1 + 2 + 3.)

If n goes from 10 to 100, roughly how much do the steps increase for an algorithm with step count ~n?

If n goes from 10 to 100, roughly how much do the steps increase for an algorithm with step count ~n²?

Arrange these step counts in order of growth (slowest first):

Step count = n²
Step count = n
Step count = 1 (constant)
Step count = n × (n − 1) / 2

Edge cases

Counting constants. In practice, constants matter for actual running time (one algorithm might do 2n steps, another 5n), but for understanding growth, the constant does not change the big picture. An algorithm that does 100n steps and one that does n steps both grow linearly — they scale the same way. The next lesson introduces Big-O notation, which ignores constants and focuses on growth.

Common mistake

Forgetting nested loops. A common mistake: you see a single loop and assume the step count is linear. But nested loops change everything. A loop inside a loop is not 2n; it is n × n. A loop inside a loop inside a loop is n³. Always count the nesting.

Check yourself

Quiz

An algorithm has a step count of roughly 3n + 5. If n doubles, roughly how many times does the step count increase?

Recap

The step count of an algorithm is how many basic operations it performs on an input of size n. Different algorithms have different step counts:

A single loop through n items: step count ≈ n
Nested loops over all pairs: step count ≈ n²

As n grows, the step count grows. Linear algorithms (step count ~n) grow at a constant rate; quadratic algorithms (step count ~n²) grow much faster. What matters is the dominant term and the growth rate, not the exact number of steps or constants. The next lesson formalizes this idea with Big-O notation.

Continue the climb ↑Big-O notation