Card 04/ 08
Estimate Whether an Algorithm Finishes in Time
Put n into the growth class and compare the result with about 10⁸ simple steps a second.
You can tell whether an algorithm will finish in time before writing it, from the input size n and the algorithm's growth class. Put n into the class to count the steps, divide by about 10⁸ steps a second, and compare the answer with the time you have. This walkthrough runs that estimate for 100,000 items and a limit of one second.
You need the growth class of each algorithm you are weighing, and one rough rate. Antti Laaksonen's Competitive Programmer's Handbook puts a modern computer at some hundreds of millions of operations a second. This walkthrough uses 10⁸, the cautious end, because one step in your code is often several operations for the processor.
The task has three candidate algorithms: one O(n log n), one O(n²) and one O(2ⁿ). Which can handle n = 100,000 within one second?
Estimating time at n = 100,000
Count the steps
Put n = 100,000 into each class, with log n to base 2. n log n gives 1,660,964 steps and n² gives 10¹⁰. 2ⁿ gives a number of steps with 30,103 digits.
Convert steps to seconds
Divide each count by 10⁸. The O(n log n) algorithm needs 0.0166 seconds and the O(n²) algorithm needs 100. The O(2ⁿ) algorithm needs a number of seconds with 30,095 digits.
Compare with the limit
Set each time against the one second you have.
| Class | Steps | Seconds | Fits in one second |
|---|---|---|---|
| O(n log n) | 1,660,964 | 0.0166 | Yes |
| O(n²) | 10¹⁰ | 100 | No |
| O(2ⁿ) | A 30,103-digit number | A 30,095-digit number | No |
O(n log n) fits with room to spare. O(n²) is about 100 times too slow, and O(2ⁿ) will never finish.
Turn the estimate round
The same arithmetic run backwards gives the largest input each class handles in about a second. Laaksonen prints it as a rough guide, and each row here was checked at 10⁸ steps a second. The first row, O(n!), is n factorial: the number of different orders n items can be put in.
| Input size | Class | Steps at that size | Seconds |
|---|---|---|---|
| Up to 10 | O(n!) | 3,628,800 | 0.0363 |
| Up to 20 | O(2ⁿ) | 1,048,576 | 0.0105 |
| Up to 500 | O(n³) | 125,000,000 | 1.25 |
| Up to 5,000 | O(n²) | 25,000,000 | 0.25 |
| Up to 10⁶ | O(n log n) | 19,931,569 | 0.199 |
Above 10⁶ items, the guide asks for O(log n) or O(1). Read the table from the input size you are given to the fastest-growing class you can afford.
How you know it worked. The answer is an order of magnitude. The language, the machine and the constants a class drops can each move it several times either way. The O(n³) row shows it: 1.25 seconds is over a second, and the guide still calls 500 items a fit. So when an estimate lands within a factor of 10 of the limit, measure the real program. When it misses by a factor of 100, as O(n²) did here, no tuning will rescue it, and you need a slower-growing class.
The estimate also assumes every step is simple. A step that is O(1) but reads a disk or waits on a network can take thousands of times longer than a comparison, so count those steps separately.
← → move through sections and cards