Card 07/ 08
Practice: Classifying Costs and Checking a Time Limit
Simplify four cost expressions, rank them, then decide which one fits a stated input size.
Classifying costs takes three skills used together: simplifying a cost to its class, ranking classes by growth, and checking a class against a time limit. This exercise practises all three. Four algorithms for the same task cost these numbers of steps on n items:
- A: 5n + 3n log n
- B: n²/2 + 100n
- C: 2ⁿ + n³
- D: 7 log n + 40
- Simplify each cost to its Big O class.
- Rank the four from slowest-growing to fastest.
- The input has n = 1,000,000 items and the limit is one second. At 10⁸ simple steps a second, which algorithms fit?
Show the answers
| Cost | Class | Rank | Steps at n = 1,000,000 | Seconds | Fits in one second |
|---|---|---|---|---|---|
| D: 7 log n + 40 | O(log n) | 1 | 180 | Under 0.001 | Yes |
| A: 5n + 3n log n | O(n log n) | 2 | 64,794,706 | 0.648 | Yes |
| B: n²/2 + 100n | O(n²) | 3 | 5 × 10¹¹ | 5,001 | No |
| C: 2ⁿ + n³ | O(2ⁿ) | 4 | A 301,030-digit number | A 301,022-digit number | No |
In A, 3n log n outgrows 5n. In B, n²/2 outgrows 100n, and the half is a constant factor. In C, 2ⁿ outgrows n³: the run found 2ⁿ the larger for every n from 10. In D, the 40 is a constant.
A fits, but look at its time: 0.648 seconds, against 0.199 for n log n alone. The constants 5 and 3 more than tripled the estimate, so near a limit, work the estimate out with its constants as well as its class. B needs 5,001 seconds, well over an hour.
← → move through sections and cards