Derive: How Long Does It Take?

The base case is $n=1$. The recurrence gives $T(1)=0$, and the closed form gives $1\times {\log }_{2}1-1+1=0$, so the two agree. Now assume the closed form holds at $n/2$, where $n$ is a power of two greater than 1: $$T(n/2)=\frac{n}{2}{\log }_2\frac{n}{2}-\frac{n}{2}+1.$$ Substitute this into the recurrence: $$\begin{array}{rl}T(n)& =2\left(\frac{n}{2}{\log }_2\frac{n}{2}-\frac{n}{2}+1\right)+n-1\\ & =n{\log }_2\frac{n}{2}-n+2+n-1\\ & =n\left({\log }_{2}n-1\right)-n+2+n-1\\ & =n{\log }_{2}n-n-n+n+2-1\\ & =n{\log }_{2}n-n+1.\end{array}$$ The induction is complete: the formula holds at 1, and if it holds at $n/2$ it holds at $n$, so it holds at every power of two.

At $n=8$ the closed form gives $$T(8)=8{\log }_{2}8-8+1=8\times 3-8+1=17.$$ The lower bound uses $8!=40,320$. Now $2^{15}=32,768$ is below 40,320 and $2^{16}=65,536$ is above it, so $$\lceil {\log }_{2}40,320\rceil =16.$$ The gap is $17-16=1$. Section 5.3 built the recurrence and section 5.4 built the floor; putting them side by side says merge sort is one comparison above the floor at eight cards. The lower bound does not say that merge sort is optimal at every size, and it does not say that a procedure meeting the bound exists. It says that no comparison sort can use 15 or fewer comparisons on some order of eight cards.

Evaluate the cost at twice the size: $$C(2n)=(2n{)}^2+2n=4n^2+2n=2n(2n+1).$$ The cost at $n$ is $$C(n)=n^2+n=n(n+1).$$ Divide the first by the second: $$\frac{C(2n)}{C(n)}=\frac{2n(2n+1)}{n(n+1)}=\frac{2(2n+1)}{n+1}=\frac{4n+2}{n+1}.$$ Write $4n+2=4(n+1)-2$ to get $$\frac{C(2n)}{C(n)}=4-\frac{2}{n+1}.$$ At $n=1$ the ratio is $4-1=3$. At $n=2$ it is $4-\frac{2}{3}=\frac{10}{3}\approx 3.333$. At $n=4$ it is $4-\frac{2}{5}=\frac{18}{5}=3.6$. For every finite positive $n$ the subtracted term is positive, so the ratio is below 4. As $n$ grows, $\frac{2}{n+1}$ tends to zero and the ratio tends to 4.

The example is a counterexample to reading “about four” as an exact rule. At $n=1$ the quadratic cost grows by a factor of 3, which is 25 per cent below 4. At $n=4$ it is 10 per cent below. The word about in section 5.2 is doing real work: the doubling rule is an asymptotic statement, and its error is largest at the small sizes where a program often runs. A reader who uses the rule to predict a factor of exactly four at $n=1$ gets the wrong number.

Base. At $n=10$ the left side is $2^{10}=1,024$ and the right side is $10^3=1,000$, so the inequality holds.

Induction step. Assume $2^n>n^3$ for some $n\ge 10$. Multiply both sides by 2: $$2^{n+1}=2\cdot 2^n>2n^3.$$ It remains to show $2n^3\ge (n+1{)}^3$. Expand the difference: $$2n^3-(n+1{)}^3=n^3-3n^2-3n-1.$$ At $n=4$ this is $64-48-12-1=3$, which is positive. The derivative of $n^3-3n^2-3n-1$ is $3n^2-6n-3=3(n^2-2n-1)$, which is positive for $n>1+\sqrt{2}\approx 2.414$. The difference therefore increases for $n\ge 4$ and stays positive, so $2n^3\ge (n+1{)}^3$ for every $n\ge 4$. Combining the two inequalities gives $$2^{n+1}>(n+1{)}^3.$$ By induction, $2^n>n^3$ for every whole $n\ge 10$.

The ratio. Write $r_n=2^n/n^3$. Then $$\frac{r_{n+1}}{r_n}=\frac{2^{n+1}/(n+1{)}^3}{2^n/n^3}=\frac{2n^3}{(n+1{)}^3}=2{\left(\frac{n}{n+1}\right)}^3.$$ As $n$ grows, $\frac{n}{n+1}$ tends to 1, so the ratio tends to 2. The sequence $r_n$ is positive and increasing for $n\ge 4$, because the ratio is above 1 there. If $r_n$ converged to a finite positive limit, the ratio of successive terms would tend to 1. It tends to 2 instead, so $r_n$ has no finite limit and grows without bound.

The result turns the table in section 5.6 into a statement about every size, not only the four sizes the table shows. The cubic column is not close to the exponential column in the long run, and the gap widens without limit. The proof covers the cubic specifically; it does not by itself compare $2^n$ with every polynomial, and it says nothing about the constants at small $n$, where the two columns can sit close together.