Counting Steps

Lesson 1 of 11 · 5 min · Free, no account needed

What you will learn

The step count is how many basic steps a program takes. It grows with the size of the data, n.
One loop over n items takes about n steps: double n, double the steps.
A loop inside a loop takes about n x n steps: double n, four times the steps.
So you can predict the running time on a million items from the code alone.

Your code works on 10 songs. On a million it freezes. Could you predict that?
Two programs, the same 10 songs. Run them and watch the counters.
Now 20 songs instead of 10. Where will the pairs counter stop?
It said 100 for 10 songs. A guess is fine.
Double the songs again and again.
Watch the row and the square. Go all the way to 160.
The pairs program runs its inner loop n times for each of n values of i. That's n x n. With 2n songs it is 2n x 2n = 4 x n x n.
Counting steps.
The step count is how many basic steps a program takes, like comparing two songs. We write the size of the data as n.
One loop over n items: about n steps. Double n and the steps double.
A loop inside a loop: about n x n steps. Double n and the steps grow 4 times. That growth is the program's running time in disguise.
Predict the counter.
Each program adds 1 to steps. Guess the final count, then Run. Build a streak.
How many songs are in your library?
Roughly is fine. See how long each program takes on it.
Your library grows 10 times. Which program freezes?
Tap a program, then Check.
The scan grows like n, so 10n songs take 10 times as long. The pairs grow like n x n, so 10n songs take 10 x 10 = 100 times as long.

Lessons are interactive and need JavaScript. Turn it on to play them.