How Slow Will It Get? Counting Steps

Count the steps a loop takes instead of timing it in seconds, call the amount of data n, and watch a loop's steps grow right along with n.

Novice · Software Development · Updated

By

After this lesson you can

  • Count the steps a loop takes for a given amount of data
  • Explain why Big-O counts steps instead of measuring seconds

Key takeaways

  • A step is one small action the code takes, such as looking at one item or comparing two values.
  • Developers call the amount of data n. A loop that looks at every item once takes n steps.
  • Counting steps gives the same answer on every computer, which is why Big-O counts steps, not seconds.

A teammate asks you, "how slow does the search get when the playlist grows?" You could time it on your laptop, but your teammate's laptop will give a different number, and a phone a third. There is an answer that's the same on every machine: count the steps. In this lesson you count the steps of a real loop, and the count tells you how the search grows before anybody has to wait for it.

What counts as a step

A step is one small action the code takes, the kind a computer does in about the same time whatever it's working on:

  • looking at one item on a list
  • comparing two values, such as two song titles
  • adding one to a counter

You don't count every keystroke of the code. You count the action that repeats, because that's where the time goes. Think of climbing stairs: to compare two buildings, you count the stairs, not the seconds it took one particular person to climb them.

Calling the amount of data n

The number that grows is the amount of stuff: the songs on the playlist, the guests on a list. Developers call it n, read "en", and in textbooks the amount of data is called the input size. A playlist of 1,000 songs has n = 1,000.

The question from Twice the Stuff, How Much More Work? becomes: when n doubles, what happens to the number of steps?

Counting the steps of a search

Here's a search that reads titles from the top of a playlist until it finds the one it wants. A counter, reads, goes up by one for every title it looks at. The playlists are made up (Song 1, Song 2, and so on), and the song it looks for, Golden Hour, isn't on any of them, so the search has to read every title before it can give up:

List<string> MakePlaylist(int songCount)
{
    List<string> playlist = new List<string>();
    for (int number = 1; number <= songCount; number++)
    {
        playlist.Add("Song " + number);
    }
    return playlist;
}

int TitlesRead(List<string> playlist, string title)
{
    int reads = 0;
    foreach (string song in playlist)
    {
        reads++;
        if (song == title)
        {
            break;
        }
    }
    return reads;
}

foreach (int songCount in new int[] { 1000, 2000, 4000 })
{
    List<string> playlist = MakePlaylist(songCount);
    Console.WriteLine("Songs: " + songCount + ", titles read: " + TitlesRead(playlist, "Golden Hour"));
}
Songs: 1000, titles read: 1000
Songs: 2000, titles read: 2000
Songs: 4000, titles read: 4000
List<String> makePlaylist(int songCount) {
    List<String> playlist = new ArrayList<>();
    for (int number = 1; number <= songCount; number++) {
        playlist.add("Song " + number);
    }
    return playlist;
}

int titlesRead(List<String> playlist, String title) {
    int reads = 0;
    for (String song : playlist) {
        reads++;
        if (song.equals(title)) {
            break;
        }
    }
    return reads;
}

void main() {
    for (int songCount : new int[] {1000, 2000, 4000}) {
        List<String> playlist = makePlaylist(songCount);
        IO.println("Songs: " + songCount + ", titles read: " + titlesRead(playlist, "Golden Hour"));
    }
}
Songs: 1000, titles read: 1000
Songs: 2000, titles read: 2000
Songs: 4000, titles read: 4000
def make_playlist(song_count):
    playlist = []
    for number in range(1, song_count + 1):
        playlist.append(f"Song {number}")
    return playlist


def titles_read(playlist, title):
    reads = 0
    for song in playlist:
        reads += 1
        if song == title:
            break
    return reads


for song_count in [1000, 2000, 4000]:
    playlist = make_playlist(song_count)
    print(f"Songs: {song_count}, titles read: {titles_read(playlist, 'Golden Hour')}")
Songs: 1000, titles read: 1000
Songs: 2000, titles read: 2000
Songs: 4000, titles read: 4000
function makePlaylist(songCount) {
  const playlist = [];
  for (let number = 1; number <= songCount; number++) {
    playlist.push(`Song ${number}`);
  }
  return playlist;
}

function titlesRead(playlist, title) {
  let reads = 0;
  for (const song of playlist) {
    reads++;
    if (song === title) {
      break;
    }
  }
  return reads;
}

for (const songCount of [1000, 2000, 4000]) {
  const playlist = makePlaylist(songCount);
  console.log(`Songs: ${songCount}, titles read: ${titlesRead(playlist, "Golden Hour")}`);
}
Songs: 1000, titles read: 1000
Songs: 2000, titles read: 2000
Songs: 4000, titles read: 4000
function makePlaylist(songCount: number): string[] {
  const playlist: string[] = [];
  for (let number = 1; number <= songCount; number++) {
    playlist.push(`Song ${number}`);
  }
  return playlist;
}

function titlesRead(playlist: string[], title: string): number {
  let reads = 0;
  for (const song of playlist) {
    reads++;
    if (song === title) {
      break;
    }
  }
  return reads;
}

for (const songCount of [1000, 2000, 4000]) {
  const playlist = makePlaylist(songCount);
  console.log(`Songs: ${songCount}, titles read: ${titlesRead(playlist, "Golden Hour")}`);
}
Songs: 1000, titles read: 1000
Songs: 2000, titles read: 2000
Songs: 4000, titles read: 4000

The loop looks at each title once, so the steps match the songs exactly: n songs, n steps. Double n, and the steps double.

A row of eight song boxes with an arrow reading them one at a time from the left, and a counter above each box going 1, 2, 3 up to 8: one title read is one step, so eight songs take eight steps

Try it. Change the title the search looks for from "Golden Hour" to "Song 1" and run it again. Every playlist now needs only 1 read, because the song is first. The lesson Fast in the Demo, Slow for Users: Best, Worst and Average is about exactly this difference.

Why steps and not seconds

Time the search above on your computer, and you'll get a few thousandths of a second. On someone else's computer it might be half that, or ten times as much. Neither number tells you what happens when the playlist grows.

The step count does. It's the same on every computer, and it shows the pattern right away: the steps grow in step with n. That pattern, how the steps grow as n grows, is what textbooks call an algorithm's time complexity, and Big-O is how it's written down. Seconds still matter in real life, and the lesson Is It Really Slow? Measure Your Own Code times real code. But to predict what happens with more data, count steps.

Check yourself

2 questions to try on the lesson page.

So what

Whenever you see a loop over a list, you can now count its steps in terms of n, without running it. That count is the raw material for every Big-O answer in this course.

Key terms

Cheat sheets