How fast is it? Counting the work

What you will be able to do

After this lesson you can

• count the work of a method instead of timing it,
• compare how the work grows when the list grows,
• predict that doubling a list makes bubble sort four times slower, and
• decide when a faster method is worth the trouble.

Fast or slow?

You have two ways to search, and several ways to sort. Which is better? "Faster" is the answer, but how do we measure it? We could use a stopwatch. But the time depends on the computer, on what else it is doing, and on the program around it. A better way is to count the work: how many checks or comparisons the method makes, as the list gets longer.

Let n be the number of items. We ask: how does the number of steps depend on n?

Counting the checks

Predict first, then run it. Look at the columns.

• Linear search needs n checks in the worst case. 10 items, 10 checks. A million items, a million checks. The work grows in step with the list.
• Binary search needs about as many checks as the number of times you can halve n. 10 items, 4 checks. A million items, 20. The work grows very slowly. A list that is 1000 times longer needs only 10 more checks.
• Bubble sort compares neighbours in $(n - 1) + (n - 2) + \ldots + 1$ pairs, which is $n(n-1)/2$. For 10 items, 45 comparisons. For 100 items, 4950. For 1000 items, 499 500. For a million, about 500 billion. The work grows with the square of n.

Doubling the list

What happens to the work when the list becomes twice as long?

The last row is the important one: if sorting 1000 items takes one second with bubble sort, sorting 2000 takes about four seconds, and 10 000 items takes about a hundred. This is why sorting a big list with a slow method is a disaster, while the same list is no problem for a fast method. Python's sorted needs only about $n \times \log_2 n$ comparisons: for a million items, about 20 million, and not 500 billion.

A real count

The numbers above come from a formula. Does a real program agree? Let us count the comparisons that bubble sort makes on random lists.

The bubble sort curve leaves the picture early. That steep climb is why nobody sorts a big list with it.

When does it matter?

• A short list (tens of items): nobody can tell the difference. Choose the simplest method that is correct.
• A long list (thousands or more): the growth of the work decides everything. A method that is fine at 100 items can be too slow at 100 000.
• Many repeats: if you search the same list a thousand times, sorting once and then using binary search wins.

A rule of thumb for a programmer: make it correct first, then make it fast, and only if it is too slow. A clever method that is wrong is worse than a simple one that is right.

Why count and not time?

Timing depends on the machine and on luck. A count does not. If a friend says "my program took 3 seconds", you cannot compare it with yours. If a friend says "my method needs n squared steps", you know how it behaves on any computer, for any n.

Common mistakes

• Judging a method from one short list. For ten items, all methods are fast.
• Thinking that "twice as long" means "twice the work". For bubble sort it is four times.
• Optimising too early. Do not make a program complicated to save time that nobody would notice.
• Forgetting the price of sorting when you use binary search once.
• Mixing up the checks and the items. 20 checks for a million items is the number of steps, not the number of items.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

1. Warm-up. Open the problem How fast is binary search? and think about the list of a billion items.
2. Build. Open the lab Count the work. You write a function that counts the checks of linear search, and one that counts the steps of binary search.
3. Stretch. Open the problem Double the list and predict the counts before you run the program.

Remember these

• Count the work, as a function of the length n.
• Linear search: n. Binary search: about the number of halvings. Bubble sort: about n squared over two.
• Doubling the list doubles linear search, adds one step to binary search, and multiplies bubble sort by four.
• Make it correct first. Make it fast only if it is too slow.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. About how many checks does binary search need for a billion items?

2. If bubble sort needs 100 comparisons for a list, about how many does it need for a list twice as long?

3. Why do we count steps, and not seconds?