Algorithm efficiency

Watch the work pile up

Two ways to add up 1 to 10

Both methods get the right answer. The question is how much work each one does to get there. count A and count B tally the calculations each method carries out: every +, × or ÷ counts as one.

Before you press Play: which method do you think will do more work?

 1  // Method A: add the numbers one at a time
 2  total ← 0
 3  FOR i ← 1 TO n
 4     total ← total + i
 5  ENDFOR
 6  OUTPUT total
 7  // Method B: use a formula
 8  answer ← n * (n + 1) / 2
 9  OUTPUT answer

Predict, then check

Back to Methods A and B from the top of the page.

Try n = 3. Method A does 3 additions (1 + 2 + 3), and Method B does 3 calculations. It's a dead heat! Now make n = 1,000. What happens to the two counts?

When the data changes the work

Best case, worst case, or in between?

How many characters does the algorithm have to check for each password? Sort each one.

6 of 6 still to sort.

A new job. An algorithm checks whether a 6-character password contains a digit. It looks at the characters one at a time from the left, and stops as soon as it finds a digit. If it reaches the end without finding one, the answer is no. Method A always did one addition per number; this algorithm's work depends on the password itself.

What you need to know

• A problem can usually be solved by more than one algorithm. They can all give the correct result but need very different amounts of work.
• An algorithm's efficiency is about how quickly it completes its task, judged by counting its basic steps (such as comparisons or loop repetitions), not by timing it on one particular computer.
• Counting steps is a fair comparison because the count doesn't depend on the hardware.
• To compare two algorithms, count the steps each one does on the same input, then look at how that count grows as the input gets bigger. The one whose count grows more slowly is more efficient.
• The more efficient algorithm reaches the same result by doing less, for example checking fewer items or repeating a loop fewer times.
• The number of steps can depend on the data. The best case is the fewest steps possible; the worst case is the most steps possible.
• Efficiency differences matter most with large amounts of data. On a small input, two algorithms may perform similarly.

The big picture

Most problems can be solved by more than one algorithm, and they can all be correct while needing very different amounts of work. We judge an algorithm's efficiency by counting the basic steps it carries out, like comparisons or loop repetitions, rather than timing it on one particular computer. To compare two algorithms, count their steps on the same input, then look at how those counts grow as the input gets bigger: the one whose count grows more slowly is more efficient. The step count can also depend on the data itself, which is why we talk about best and worst cases.

⚠ Watch out

Comparing two algorithms on different inputs, for example one on a list of 5 items and the other on a list of 500. The step counts only mean something when both algorithms get the same input.

Memory hook

Don't time it, count it. Then make the input bigger and count again.

Check yourself

Cover the page. What does efficiency measure, and why not just time it? How do you compare two algorithms fairly? What are best and worst cases? Why does big data matter?