Lesson 7.1

Efficiency is measured against input size

Part 7: AlgorithmsReading, about 6 min2 exercises in this lesson

Algorithm efficiency: count steps against input size

By the end of this you will be able to explain what the efficiency of an algorithm means, and why it is measured by counting steps against the size of the input, not by timing a run with a clock.

Here is an algorithm that adds up the whole numbers from 1 to n. Follow it for n = 3: the box that adds to the total runs three times, once for each number.

Now make n bigger. The loop goes round once per number, so the adding box runs n times.

n	Additions to the total
10	10
100	100
1000	1000

The size of the input, n, decides how much work there is. That is the idea this whole part is built on.

What efficiency means

The efficiency of an algorithm is how much of the computer's resources it uses as the input grows. The two resources that matter most are time, meaning how many steps it takes, and space, meaning how much memory it needs. An efficient algorithm uses few of them, even when the input is large.

So efficiency is not one number. It is a link between two things: the size of the input, which we call n, and the amount of work. The table above is that link for the adding algorithm: the additions grow in step with n.

Counting steps you can check

You do not need to trust the table. This program adds up 1 to 1000 and counts its own additions as it goes.

n = 1000
total = 0
additions = 0
for i in range(1, n + 1):
    total = total + i
    additions = additions + 1
print("Total: " + str(total))
print("Additions: " + str(additions))

public static void main(String[] args) {
    int n = 1000;
    int total = 0;
    int additions = 0;
    for (int i = 1; i <= n; i++) {
        total = total + i;
        additions = additions + 1;
    }
    System.out.println(
        "Total: " + total);
    System.out.println(
        "Additions: " + additions);
}

It prints:

Total: 500500
Additions: 1000

Change the first line to 10 or 100 and run it again: the number of additions always equals n.

To count steps, pick the one step that is repeated most, here the addition to the total, and count how often it runs. The loop also compares i with n and adds 1 to i on every turn, but those grow in the same way, so counting one of them tells you how the work grows.

Why not use a clock?

You could time the program instead. But a time in seconds depends on much more than the algorithm:

The computer. A new laptop runs the same program faster than an old phone.
What else is running. Other programs share the processor, so the same run can take longer one minute than the next.
The language and its version. The same steps can take a different time in Python and in Java.
The input. A time for 1000 numbers says nothing on its own about 1000000 numbers.

A step count avoids all of this. The program above makes 1000 additions for n = 1000 on every computer, in either language, on a quiet day or a busy one. And because the count is written in terms of n, it tells you what happens as the input grows, which one time on one input cannot.

Same task, different efficiency

There is another way to add up 1 to n. A formula gives the answer straight away: n times (n + 1), halved. For n = 1000 that is 1000 times 1001, halved, which is 500500, the same total.

The formula uses one multiplication, one addition and one division whatever n is: 3 steps for n = 10, and still 3 steps for n = 1000. The loop uses n additions. Both are correct, but as n grows the formula's work stays the same while the loop's work grows with n. That difference is what we mean when we say one algorithm is more efficient than another.

Explaining it in an answer

When a question asks why efficiency is measured against input size, make two points.

A step count depends on the algorithm and its input, not on the computer, so it is the same on any machine. A time also depends on the machine, other programs and the language.
Written in terms of n, it shows how the work grows as the input grows, so you can predict a larger input. One timing is for one input size only.

Now try it yourself on the questions below.

Exercise 7.1.17.1.1 · Answer itTiming on two computers

Aiko and Ben run the same program, which checks a list of names for a typing mistake. It looks at each name once.

Aiko runs it on her old laptop with a list of 5000 names. It takes 0.9 seconds.
Ben runs it on his new computer with a list of 20000 names. It takes 0.6 seconds.

Ben says his run shows that the program copes better with bigger lists.

(a) State what is meant by the efficiency of an algorithm. [1]

(b) Explain why the two times cannot be compared to judge the program's algorithm. [2]

(d) Use your answer to (c) to explain why Ben's claim is wrong. [1]

[5]

Your answer

Exercise 7.1.27.1.2 · Answer itCount the comparisons

This function counts how many race times in a list are over a limit. Each time is a whole number of seconds.

def count_over(times, limit):
    over = 0
    for t in times:
        if t > limit:
            over = over + 1
    return over

public static int countOver(
        int[] times, int limit) {
    int over = 0;
    for (int t : times) {
        if (t > limit) {
            over = over + 1;
        }
    }
    return over;
}

Count the comparison t > limit as one step.

(a) State how many times the comparison runs for a list of 200 times. [1]

(b) State, in terms of n, how many times the comparison runs for a list of n race times. [1]

(c) On Mei's laptop, a list of 2000 times takes 6 milliseconds. Assume the time grows in step with the number of comparisons. Estimate the time for a list of 20000 times on the same laptop. [1]

(d) The function is run on a list of 2000 times that are all over the limit, and then on a list of 2000 times that are all under it. State how many comparisons each run makes, and explain why. [2]

[5]

Your answer