Study material generated by AI from this openly licensed book (CC BY-NC 3.0). Not affiliated with or endorsed by the publisher.
Think Python, 2nd Edition, by Allen B. Downey, Green Tea Press, licensed under CC BY-NC 3.0. Read the original free
Chapter 21 · pp. 223–244
Analysis of algorithms is the study of how well a program's method performs, mainly in how long it runs and how much memory it needs. The practical goal is to predict performance so you can choose a good design before you build it. This chapter explains what the analysis is for, the problems that make comparisons tricky, and how comparing growth rates solves them.
Analysis of algorithms is a branch of computer science. It studies the run time and the space (memory) an algorithm requires (p. 223). Instead of guessing which program is faster, you count the steps each one takes and reason from there.
The point is to guide decisions. If you know ahead of time that one method will be too slow, you can pick another method early. A well-known example: in 2008 a presidential candidate was joking asked for the best way to sort a million 32-bit integers. He said bubble sort would be the wrong choice. He was right. Bubble sort is easy to understand, but it is slow on large data sets. A method called radix sort is the answer the questioner probably wanted (p. 223).
Another practical lesson is that you usually do not need to invent a sorting method. In most programs, the sort function built into your language is good enough. If the program turns out to be too slow, measure first with a profiler to see where the time goes. Only then look for a faster algorithm (p. 223).
The goal is a meaningful comparison between algorithms. Three problems get in the way, and each has a standard fix (pp. 223–224).
1. Hardware. One algorithm may be faster on Machine A, and another faster on Machine B. The fix is to choose a machine model, which is a simple set of rules for what counts as one operation. Then you count the number of steps or operations the algorithm needs under that model. You count steps, not seconds on a stopwatch (p. 223).
2. The data. Some sorting algorithms run faster when the list is already partly sorted. Others run slower in that case. A common fix is to analyze the worst case, the input that makes the algorithm work hardest. You can also study the average case, but that is usually harder. It is also not always clear which set of inputs you should average over (pp. 223–224).
3. Problem size. A method that is fast for a short list may be slow for a long one. The usual fix is to write the run time (or number of operations) as a function of the problem size, called . Then you group functions into categories by how fast they grow as increases (p. 224).
This approach makes it easy to classify algorithms. Suppose Algorithm A takes time proportional to , and Algorithm B takes time proportional to . Then A is expected to be faster than B, at least when is large (p. 224). There are some caveats to this kind of analysis, which come up later.
Suppose you find that Algorithm A takes steps and Algorithm B takes steps. Here is how they compare (p. 224):
| Input size | Algorithm A | Algorithm B |
|---|---|---|
| 10 | 1,001 | 111 |
| 100 | 10,001 | 10,101 |
| 1,000 | 100,001 | 1,001,001 |
| 10,000 | 1,000,001 | 100,010,001 |
At , A takes almost 10 times as long as B. At they are about equal. After that, A is far better, and the gap keeps growing (p. 224).
Leading term. The leading term is the term with the highest exponent. In it is . In it is . For large , a function with an term outgrows one whose leading term is only (p. 224).
Coefficients. A has a big coefficient, 100, and that is why B wins for small . But coefficients cannot rescue B forever. For any positive numbers and , there is some beyond which (p. 224).
Non-leading terms. The same idea applies to the other terms. Even if A took steps, it would still beat B once is large enough. A huge constant only delays the point where A wins (p. 224).
Crossover point. In general, the algorithm with the smaller leading term is expected to be better for large problems. For small problems there may be a crossover point, the size where the better algorithm changes. Where it falls depends on the algorithms, the inputs, and the hardware, so analysis usually ignores it. But you should not forget it. For small inputs, the "slower" algorithm may actually be the better pick (p. 224).
