Counting steps

Two programs can both be correct while one takes a second and the other takes a day. To compare them before you run them, count the steps each one takes, and see how that count grows as the input grows.

Why count steps, not seconds

You could time a program with a stopwatch. But the time depends on the computer, on what else it is doing, and on the language. A faster laptop makes every program faster, and it does not tell you which program is better.

So we count steps instead. The count depends only on the program and its input. We write n for the size of the input, such as the length of a list. Then we ask: as n grows, how fast does the number of steps grow?

What counts as one step

One step is any small action that takes about the same time whatever the input is. For example:

• adding, comparing or assigning two numbers;
• reading or writing a[i];
• calling a function (not counting the work inside it) and returning.

Some single lines of Python are not one step. x in a on a list checks values one by one, so it can take n steps. a[1:] copies n − 1 values. sorted(a) takes about n log₂ n steps. Lesson 8 lists these hidden costs.

We do not try to count exactly. Whether a comparison is one step or three does not change how the count grows. That is why the next lesson drops the constant numbers.

Loops multiply

A loop that runs n times, doing a few steps each time, does about n steps. A loop inside a loop runs its inner part n times for each of the n outer passes, which is n × n = n² steps. Step through the three versions:

n = 4
count = 0
for i in range(n):
    count += 1
print(count)

The third version is common. It compares each pair of values once: the inner loop starts after i. Its inner loop runs n − 1, then n − 2, and so on down to 0 times. The sum is:

Here is why. Write the sum forwards and backwards, one under the other. Each of the n columns adds up to n − 1, so two copies of the sum make n(n − 1). One copy is half of that. For n = 4 it gives 6. For n = 1,000 it gives 499,500, which is about half of n².

Best, worst and average case

The step count can depend on the values, not only on n. Take a search that stops when it finds the target:

def find(a, t):
    for i in range(len(a)):
        if a[i] == t:
            return i
    return -1

• Best case: the target is at index 0. One comparison.
• Worst case: the target is missing. n comparisons.
• Average case: if the target is in the list and every position is equally likely, about n/2 comparisons.

Unless we say otherwise, this course gives the worst case. It is a promise: the program never takes longer than this. The best case is rarely useful, because it describes the luckiest input. The average case needs a guess about what inputs are likely, and that guess may be wrong. In practice the tests try hard to give you the worst case.

Now try BIGO-P2, Count the steps. It asks you to count a loop like this without running it.