Lesson 8 of 11
How the count grows
Show on a big screenA rain archive is a store of past rain records. It grows every monsoon. How do the counts grow with it?
Step 1 of 4
- 8 items: walk 8, halving 4, sort 28.
- 16 items: walk 16, halving 5, sort 120.
- 32 items: walk 32, halving 6, sort 496.
- 64 items: walk 64, halving 7, sort 2016.
The rule
Double the list and watch each count. The walk doubles. Halving adds one. Selection sort grows about four times.
Each count has its own shape. A walk grows as fast as the list. Halving grows very slowly. Selection sort grows much faster.
| Items | Walk | Halving | Selection sort |
|---|---|---|---|
| 8 | 8 | 4 | 28 |
| 16 | 16 | 5 | 120 |
| 32 | 32 | 6 | 496 |
| 64 | 64 | 7 | 2,016 |
The sort's count is n × (n − 1) ÷ 2. Double n and it grows about four times. That is because the formula multiplies n by almost n.
A big list makes this sort very slow. Big lists need faster sorting methods.
Double the list. Pick the count that changed.
Loading lab…
Try the lab to finish this lesson.