Practise: How Long Does It Take?

For $n=12$ items the scan compares each item with the best so far, which is $12-1=11$ comparisons. In the worst case every comparison finds a larger item, so the scan also performs 11 replacements. The total is $11+11=22$ steps, which is $2(n-1)=2\times 11$. The worst case is a list in increasing order: each new item beats the previous best. On a decreasing list the scan still performs 11 comparisons but replaces only once, for 12 steps. The gap between 12 and 22 is the difference between one trace and a promise about every list.

At $n=17$ the linear cost is $20\times 17+7=347$ and the quadratic cost is $17^2+3\times 17+2=289+51+2=342$. The linear procedure is ahead by 5 steps. At $n=18$ the linear cost is $360+7=367$ and the quadratic cost is $324+54+2=380$. The quadratic procedure is ahead by 13 steps. The exact crossing solves $$n^2+3n+2=20n+7,$$ which rearranges to $n^2-17n-5=0$. The positive root is $$n=\frac{17+\sqrt{289+20}}{2}=\frac{17+\sqrt{309}}{2}\approx \mathrm{17.289.}$$ Below that value the quadratic cost is smaller, and above it the quadratic cost is larger. The smallest whole size above the crossing is 18. The notation hides this crossing point, and the example shows why a class alone does not tell you which procedure wins at a particular size.

The ratio of the two sizes is $40/10=4$. For a cubic cost the ratio of the work is the cube of the size ratio, so the factor is $4^3=64$. The cost at 40 is therefore $64\times 1,000=64,000$ steps. Direct evaluation agrees: $40^3=64,000$. Quadrupling the input multiplies a cubic cost by 64, while it multiplies a linear cost by 4 and a quadratic cost by 16. The response to the same change of size is what separates the rungs.

Put $n=64$ into the closed form: $$T(64)=64{\log }_{2}64-64+1=64\times 6-64+1=384-64+1=321.$$ The recurrence gives the same value one level at a time: $T(2)=2\times 0+1=1$, $T(4)=2\times 1+3=5$, $T(8)=2\times 5+7=17$, $T(16)=2\times 17+15=49$, $T(32)=2\times 49+31=129$, and $T(64)=2\times 129+63=321$. The table is the smallest check that the closed form reads correctly. The logarithm counts the six levels of the recursion tree, and the linear terms count the merging on each level.

Unrolling gives $$T(10)=9+T(9)=9+8+T(8)=\cdots =9+8+\cdots +1+T(1).$$ Since $T(1)=0$, the cost is the sum of the integers from 1 to 9: $$T(10)=\frac{9\times 10}{2}=45.$$ The closed form is $T(n)=n(n-1)/2$, which grows like $n^2/2$. The even split at $n=8$ costs 17 comparisons, while the uneven split at $n=10$ already costs 45. The comparison is the point of the exercise: the recurrence is the same shape in both cases, and the split decides whether the tree has a logarithmic number of levels or a linear number.

Five different cards have $5!=120$ possible orders. A comparison has two outcomes, so a procedure that asks $k$ comparisons can reach at most $2^k$ leaves. To name one of 120 orders it needs at least 120 leaves, so $2^k\ge 120$. Now $2^6=64$, which is below 120, and $2^7=128$, which is above it. The smallest whole $k$ is therefore 7. The logarithm gives the same count: ${\log }_{2}120\approx 6.907$, and the next whole number is 7. The argument says seven comparisons are necessary. It does not say that every procedure using seven comparisons is correct; it sets a floor under every comparison sort at once.

The Fibonacci numbers from $F_1$ to $F_{13}$ are $$1,1,2,3,5,8,13,21,34,55,89,144,233.$$ The call count at $n=12$ is $$C(12)=2F_{13}-1=2\times 233-1=465.$$ The table procedure needs $n-1=11$ additions, so the naive recursion makes about $465/11\approx 42.3$ calls for every addition the table performs. The ratio is not constant: it grows with $n$, because the call count follows the Fibonacci numbers while the table count follows $n$. That growing ratio is the exponential rung meeting the linear rung.

The number of settings is $$2^{50}=1,125,899,906,842,624.$$ At $10^9$ checks per second the search takes $$\frac{1,125,899,906,842,624}{10^9}=1,125,899.906842624$$ seconds. Divide by 86,400 seconds per day: $$\frac{1,125,899.906842624}{86,400}\approx 13.0312$$ days, which rounds to 13.03 days. Section 5.6 reports about 36 years at sixty switches. Moving from fifty to sixty switches multiplies the count by $2^{10}=1,024$, and $13.03\times 1,024\approx 13,344$ days, which is about 36.5 years. The chapter rounds that to 36 years. The two reports come from the same rule, applied at two sizes.