A puzzle sold as the Tower of Hanoi has three pegs and a stack of discs of different sizes on the first peg, largest at the bottom. A move takes the top disc of one peg and places it on another peg, never on top of a smaller disc. The task is to move the whole stack to the third peg. A legend attached to the puzzle speaks of a temple in which priests are moving a stack of \(64\) golden discs, one move per second, and says that the world will end when they finish. How worried should we be?
The answer needs two things. The first is a formula for the least number of moves for \(n\) discs. No direct description of that number is apparent, but there is an obvious relation between the problem for \(n\) discs and the problem for \(n-1\) , and the relation determines the number. A rule that defines each term of a sequence from earlier terms is a recurrence. The second is a sense of how large the formula’s value is: whether the number for \(64\) discs is the size of a lifetime or of the age of the universe. That is a question about growth. This chapter treats both: how to solve the commonest kinds of recurrence exactly, and how to compare the growth of functions when exact values matter less than the order of magnitude.
7.1 Sequences defined by their past
Definition 7.1 (recurrence). A recurrence of order \(k\) for a sequence \(a_0,a_1,a_2,\dots\) is a rule that expresses \(a_n\) , for every \(n\ge k\) , in terms of the \(k\) preceding terms \(a_{n-1},\dots,a_{n-k}\) and possibly \(n\) . The values \(a_0,\dots,a_{k-1}\) are the initial conditions. A closed form for the sequence is a formula giving \(a_n\) directly in terms of \(n\) .
The Fibonacci numbers of Example 3.5 are defined by a recurrence of order \(2\) with initial conditions \(F_0=0\) and \(F_1=1\) .
Proposition 7.2 (a recurrence determines its sequence). If two sequences satisfy the same recurrence of order \(k\) and have the same initial conditions, then they are equal. Consequently, to prove that a formula is a closed form for a sequence defined by a recurrence, it suffices to check that the formula satisfies the initial conditions and satisfies the recurrence.
Proof. Let \((a_n)\) and \((b_n)\) be the two sequences, and let \(P(n)\) be the statement \(a_n=b_n\) . The cases \(n=0,\dots,k-1\) hold because the initial conditions agree. For \(n\ge k\) , if \(a_j=b_j\) for all \(j<n\) , then \(a_n\) and \(b_n\) are computed by the same rule from the same \(k\) preceding values, so \(a_n=b_n\) . By strong induction \(a_n=b_n\) for all \(n\) . For the second statement, the sequence given by the formula and the sequence defined by the recurrence satisfy the same recurrence with the same initial conditions.
The proposition licenses the method of guess and verify: compute a few terms, guess a formula, and check the two conditions. The check is an induction, but the proposition has done the induction once and for all.
Example 7.1: The Tower of Hanoi
Let \(T_n\) be the least number of moves that transfers a stack of \(n\) discs from one peg to another. Clearly \(T_0=0\) and \(T_1=1\) .
An upper bound. To move \(n\) discs from the first peg to the third: move the top \(n-1\) discs to the second peg, in \(T_{n-1}\) moves; move the largest disc to the third peg, in \(1\) move; move the \(n-1\) discs from the second peg onto it, in \(T_{n-1}\) moves. The largest disc never obstructs the others, since any disc may be placed on it. So \(T_n\le 2T_{n-1}+1\) .
A lower bound. In any solution the largest disc must move at least once. At the moment of its first move, it is alone on its peg and its destination peg is empty, so all \(n-1\) smaller discs are stacked on the remaining peg; getting them there took at least \(T_{n-1}\) moves. After the last move of the largest disc, the \(n-1\) smaller discs are again all on one peg other than the destination, and bringing them onto the largest disc takes at least \(T_{n-1}\) moves. So \(T_n\ge 2T_{n-1}+1\) .
Hence \(T_n=2T_{n-1}+1\) for \(n\ge 1\) , a recurrence of order \(1\) . The first values are \(0,1,3,7,15,31,63\) , each one less than a power of \(2\) . Guess \(T_n=2^{n}-1\) and verify: the formula gives \(2^{0}-1=0\) , matching the initial condition, and
so it satisfies the recurrence. By Proposition 7.2, \(T_n=2^{n}-1\) for every \(n\) .
For \(64\) discs the number of moves is \(2^{64}-1=18446744073709551615\) . At one move per second this is about \(5.8\times 10^{11}\) years, roughly forty times the present age of the universe. The legend is no cause for alarm. Notice that both bounds were needed. The strategy alone shows only that \(2^{n}-1\) moves are enough; the argument about the largest disc shows that no cleverer strategy exists.
7.2 Recurrences of order one
When guessing is not easy, a first-order recurrence can be solved by unrolling: substitute the recurrence into itself until the pattern is visible. The sums that arise are geometric.
Theorem 7.3 (geometric sum). For every real number \(r\ne 1\) and every integer \(n\ge 0\) ,
Proof. Let \(S=1+r+\dots+r^{n-1}\) . Then \(rS=r+r^{2}+\dots+r^{n}\) , and subtracting, every term cancels except the last of \(rS\) and the first of \(S\) : \(rS-S=r^{n}-1\) . Divide by \(r-1\) , which is not zero. For \(n=0\) the sum is empty and both sides are \(0\) . An induction on \(n\) gives a second proof, which was Exercise 3.3.
Theorem 7.4 (first-order linear recurrences). Let \(c\) and \(d\) be real numbers, and let \(a_n=ca_{n-1}+d\) for all \(n\ge 1\) . If \(c\ne 1\) , then
If \(c=1\) , then \(a_n=a_0+nd\) .
Proof. Unrolling suggests the formula:
and Theorem 7.3 evaluates the sum. To prove it, apply Proposition 7.2. At \(n=0\) the formula gives \(a_0\) . And if \(b_n\) denotes the formula’s value, then
The case \(c=1\) is immediate: each step adds \(d\) .
Example 7.2: Two sequences unrolled
A constant added each time. Let \(a_0=1\) and \(a_n=3a_{n-1}+2\) . The terms are \(1,5,17,53,161\) . Theorem 7.4 with \(c=3\) and \(d=2\) gives
and indeed \(2\cdot 81-1=161\) . The Tower of Hanoi is the case \(c=2\) , \(d=1\) , \(a_0=0\) .
A varying amount added each time. Let \(b_0=0\) and \(b_n=b_{n-1}+n\) . Theorem 7.4 does not apply, because the added term is not constant, but unrolling still works:
Any recurrence of the form \(b_n=b_{n-1}+g(n)\) unrolls to a sum, \(b_n=b_0+g(1)+\dots+g(n)\) , and solving it means evaluating that sum.
7.3 Linear recurrences of order two
The Fibonacci recurrence does not unroll into anything useful, because each substitution doubles the number of terms. A different idea is needed.
Definition 7.5 (linear homogeneous recurrence, characteristic equation). A linear homogeneous recurrence of order two with constant coefficients has the form
where \(p\) and \(q\) are real numbers and \(q\ne 0\) . Its characteristic equation is \(x^{2}=px+q\) .
The idea is to look for solutions of a special shape. A first-order recurrence \(a_n=ca_{n-1}\) has the geometric solutions \(a_n=c^{n}a_0\) . Try a geometric sequence \(a_n=x^{n}\) , with \(x\ne 0\) , in the second-order recurrence: it is a solution exactly when \(x^{n}=px^{n-1}+qx^{n-2}\) for all \(n\ge 2\) , and dividing by \(x^{n-2}\) , exactly when \(x^{2}=px+q\) . So the roots of the characteristic equation give geometric solutions. The recurrence then lets them be combined.
Lemma 7.6 (superposition). If the sequences \((u_n)\) and \((v_n)\) both satisfy \(a_n=pa_{n-1}+qa_{n-2}\) , then so does \((Au_n+Bv_n)\) for all real numbers \(A\) and \(B\) .
Proof. For \(n\ge 2\) , \(Au_n+Bv_n=A(pu_{n-1}+qu_{n-2})+B(pv_{n-1}+qv_{n-2})=p(Au_{n-1}+Bv_{n-1})+q(Au_{n-2}+Bv_{n-2})\) .
Theorem 7.7 (solution by characteristic roots). Consider the recurrence \(a_n=pa_{n-1}+qa_{n-2}\) with \(q\ne 0\) , and suppose its characteristic equation \(x^{2}=px+q\) has real roots \(r\) and \(s\) .
(a) If \(r\ne s\) , then for any initial conditions \(a_0\) , \(a_1\) there are unique real numbers \(A\) , \(B\) such that \(a_n=Ar^{n}+Bs^{n}\) for all \(n\ge 0\) .
(b) If \(r=s\) , then for any initial conditions there are unique real numbers \(A\) , \(B\) such that \(a_n=(A+Bn)r^{n}\) for all \(n\ge 0\) .
Proof. (a) The sequences \((r^{n})\) and \((s^{n})\) satisfy the recurrence, as shown above, so by Lemma 7.6 every sequence \(Ar^{n}+Bs^{n}\) does. It matches the initial conditions exactly when
Subtracting \(r\) times the first equation from the second gives \(B(s-r)=a_1-ra_0\) . Since \(s\ne r\) , this determines \(B\) uniquely, and then \(A=a_0-B\) . With these values the sequence \(Ar^{n}+Bs^{n}\) satisfies the recurrence and the initial conditions, so it equals \((a_n)\) by Proposition 7.2.
(b) If \(r\) is a repeated root, then \(x^{2}-px-q=(x-r)^{2}\) , so \(p=2r\) and \(q=-r^{2}\) ; and \(r\ne 0\) because \(q\ne 0\) . The sequence \((r^{n})\) satisfies the recurrence as before. So does \((nr^{n})\) :
By Lemma 7.6 every sequence \((A+Bn)r^{n}\) satisfies the recurrence. It matches the initial conditions exactly when \(A=a_0\) and \((A+B)r=a_1\) , which determine \(A\) and then, since \(r\ne 0\) , \(B\) uniquely. Proposition 7.2 finishes the proof as in (a).
The method has three steps: solve the characteristic equation, write the general solution with two undetermined constants, and determine the constants from the two initial conditions. When the characteristic equation has no real root, the same formula holds with complex roots; Exercise 7 shows what such sequences look like.
Example 7.3: Distinct roots
Solve \(a_n=3a_{n-1}-2a_{n-2}\) with \(a_0=0\) and \(a_1=1\) .
The characteristic equation is \(x^{2}=3x-2\) , that is, \((x-1)(x-2)=0\) , with roots \(1\) and \(2\) . The general solution is \(a_n=A\cdot 1^{n}+B\cdot 2^{n}=A+B\,2^{n}\) . The initial conditions give \(A+B=0\) and \(A+2B=1\) , so \(B=1\) and \(A=-1\) :
The terms \(0,1,3,7,15\) are the Tower of Hanoi numbers, and this is no accident. Subtracting \(T_{n-1}=2T_{n-2}+1\) from \(T_n=2T_{n-1}+1\) eliminates the constant and gives \(T_n-T_{n-1}=2T_{n-1}-2T_{n-2}\) , which is the present recurrence. A first-order recurrence with a constant term can always be traded for a homogeneous second-order one in this way.
Example 7.4: A formula for the Fibonacci numbers
For \(F_n=F_{n-1}+F_{n-2}\) the characteristic equation is \(x^{2}=x+1\) , with roots
So \(F_n=A\varphi^{n}+B\psi^{n}\) . From \(F_0=0\) we get \(B=-A\) , and from \(F_1=1\) we get \(A(\varphi-\psi)=1\) ; since \(\varphi-\psi=\sqrt5\) , \(A=1/\sqrt5\) . Therefore
It is remarkable that this expression, full of irrational numbers, is an integer for every \(n\) . Since \(\lvert\psi\rvert<1\) , the term \(\psi^{n}/\sqrt5\) is smaller than \(\tfrac12\) in absolute value, so \(F_n\) is the integer nearest to \(\varphi^{n}/\sqrt5\) . For \(n=10\) : \(\varphi^{10}/\sqrt5\approx 55.0036\) , and \(F_{10}=55\) . The formula also shows how fast the Fibonacci numbers grow: each is about \(1.618\) times its predecessor. Example 3.5 proved the cruder bound \(F_n<2^{n}\) without knowing the formula.
Example 7.5: A repeated root
Solve \(a_n=4a_{n-1}-4a_{n-2}\) with \(a_0=1\) and \(a_1=4\) .
The characteristic equation \(x^{2}=4x-4\) is \((x-2)^{2}=0\) , with the repeated root \(2\) . By Theorem 7.7(b), \(a_n=(A+Bn)2^{n}\) . From \(a_0=1\) , \(A=1\) ; from \(a_1=4\) , \((1+B)\cdot 2=4\) , so \(B=1\) :
Check against the recurrence: \(a_2=4\cdot 4-4\cdot 1=12=3\cdot 4\) , \(a_3=4\cdot 12-4\cdot 4=32=4\cdot 8\) , \(a_4=4\cdot 32-4\cdot 12=80=5\cdot 16\) .
Using the distinct-root form \(A2^{n}+B2^{n}\) here would give a single constant in disguise and could not match two initial conditions. The factor \(n\) is what a repeated root contributes.
Recurrences are also a counting tool. When the objects of size \(n\) can be sorted by how they end, and each class corresponds to objects of smaller size, the sum rule gives a recurrence.
Example 7.6: Strings without two consecutive ones
Let \(s_n\) be the number of bit strings of length \(n\) that do not contain two consecutive ones. Sort such strings of length \(n\ge 2\) by their last bit. If the last bit is \(0\) , the first \(n-1\) bits form any valid string of length \(n-1\) : there are \(s_{n-1}\) of these. If the last bit is \(1\) , the bit before it must be \(0\) , and the first \(n-2\) bits form any valid string of length \(n-2\) : there are \(s_{n-2}\) of these. The two classes are disjoint, so
The empty string accounts for \(s_0=1\) . This is the Fibonacci recurrence with shifted initial conditions: \(s_0=F_2\) and \(s_1=F_3\) , so by Proposition 7.2, \(s_n=F_{n+2}\) . The values run \(1,2,3,5,8,13,21,34,55,89,144\) , so of the \(1024\) bit strings of length \(10\) , exactly \(144\) avoid two consecutive ones.
Deriving the recurrence was a counting argument in the style of Chapter 5: a bijection between the valid strings of length \(n\) and the disjoint union of the valid strings of lengths \(n-1\) and \(n-2\) . Solving it was algebra. Many counting problems that resist a direct formula yield in this two-stage way.
7.4 Comparing rates of growth
The Tower of Hanoi takes \(2^{n}-1\) moves. Sorting \(n\) numbers by adjacent swaps takes at most \(\frac{n(n-1)}{2}\) swaps, by Example 3.10. For small \(n\) these are comparable; for \(n=64\) one is \(2016\) and the other has twenty digits. To compare methods one wants a way of speaking that ignores constant factors and small cases and keeps only the rate of growth.
Definition 7.8 (asymptotic notation). Let \(f\) and \(g\) be functions from \(\mathbb N\) to the real numbers, with \(g(n)>0\) for all sufficiently large \(n\) .
We write \(f=O(g)\) , read “\(f\) is big-O of \(g\) ”, if there exist a real number \(C>0\) and an integer \(n_0\) such that \(\lvert f(n)\rvert\le C\,g(n)\) for all \(n\ge n_0\) .
We write \(f=\Omega(g)\) if there exist \(c>0\) and \(n_0\) such that \(f(n)\ge c\,g(n)\) for all \(n\ge n_0\) .
We write \(f=\Theta(g)\) if both \(f=O(g)\) and \(f=\Omega(g)\) .
Informally, \(O\) is an upper bound on the rate of growth, \(\Omega\) a lower bound, and \(\Theta\) says the two functions grow at the same rate. The definition of \(f=O(g)\) has the quantifier structure \(\exists C\ \exists n_0\ \forall n\ge n_0\) , and the order matters as it did in Section 1.4: one constant \(C\) must serve for all large \(n\) . To prove a statement \(f=O(g)\) , exhibit the witnesses \(C\) and \(n_0\) . To disprove it, negate: for every \(C\) and every \(n_0\) there is some \(n\ge n_0\) with \(\lvert f(n)\rvert>C\,g(n)\) ; in practice one shows that the ratio \(f(n)/g(n)\) exceeds every bound.
The equals sign in \(f=O(g)\) is a tradition and not an equality. It is read from left to right only: \(n=O(n^{2})\) is true, and nobody writes \(O(n^{2})=n\) . A more accurate notation would be \(f\in O(g)\) , where \(O(g)\) is a set of functions.
Proposition 7.9 (rules for big-O). (a) If \(f=O(g)\) and \(g=O(h)\) , then \(f=O(h)\) . (b) If \(f_1=O(g)\) and \(f_2=O(g)\) , then \(f_1+f_2=O(g)\) . (c) If \(f(n)=a_dn^{d}+a_{d-1}n^{d-1}+\dots+a_0\) is a polynomial with \(a_d>0\) , then \(f=\Theta(n^{d})\) .
Proof. (a) If \(\lvert f(n)\rvert\le Cg(n)\) for \(n\ge n_0\) and \(g(n)\le C'h(n)\) for \(n\ge n_1\) , then \(\lvert f(n)\rvert\le CC'h(n)\) for \(n\ge\max(n_0,n_1)\) .
(b) If \(\lvert f_1(n)\rvert\le C_1g(n)\) for \(n\ge n_1\) and \(\lvert f_2(n)\rvert\le C_2g(n)\) for \(n\ge n_2\) , then \(\lvert f_1(n)+f_2(n)\rvert\le(C_1+C_2)g(n)\) for \(n\ge\max(n_1,n_2)\) .
(c) Let \(M=\lvert a_{d-1}\rvert+\dots+\lvert a_0\rvert\) , with \(M=0\) if \(d=0\) . For \(n\ge 1\) each power \(n^{i}\) with \(i<d\) is at most \(n^{d-1}\) , so the terms below the leading one have absolute value at most \(Mn^{d-1}\) in total, whatever their signs. Hence \(\lvert f(n)\rvert\le a_dn^{d}+Mn^{d-1}\le(a_d+M)n^{d}\) for \(n\ge 1\) , which gives \(f=O(n^{d})\) with \(C=a_d+M\) and \(n_0=1\) . For the lower bound choose an integer \(n_0\) with \(n_0\ge 1\) and \(n_0\ge 2M/a_d\) . For \(n\ge n_0\) both estimates are available: the lower terms are at most \(Mn^{d-1}\) in absolute value because \(n\ge 1\) , and \(Mn^{d-1}\le\frac{a_d}{2}n^{d}\) because \(n\ge 2M/a_d\) . So \(f(n)\ge a_dn^{d}-Mn^{d-1}\ge\frac{a_d}{2}n^{d}\) for all \(n\ge n_0\) , which gives \(f=\Omega(n^{d})\) with \(c=\frac{a_d}{2}\) .
The next theorem places the functions that occur most often on a single scale. Logarithms are to base \(2\) : \(\log_2 n\) is the real number \(x\) with \(2^{x}=n\) , and it increases with \(n\) .
Theorem 7.10 (a hierarchy of growth). (a) \(\log_2 n=O(n)\) , and \(n\) is not \(O(\log_2 n)\) .
(b) For every positive integer \(k\) , \(n^{k}=O(2^{n})\) , and \(2^{n}\) is not \(O(n^{k})\) .
(c) \(2^{n}=O(n!)\) , and \(n!\) is not \(O(2^{n})\) .
Proof. We prove (b) first. Fix \(k\) and put \(c_n=n^{k}/2^{n}\) . Then
Now \(1+\frac1n=\bigl(1-\frac{1}{n+1}\bigr)^{-1}\) , and by Bernoulli’s inequality (Proposition 3.3), \(\bigl(1-\frac{1}{n+1}\bigr)^{k}\ge 1-\frac{k}{n+1}\) . For \(n\ge 2k\) the right side is greater than \(\frac12\) , so \(\bigl(1+\frac1n\bigr)^{k}<2\) and \(c_{n+1}<c_n\) . Thus the sequence \((c_n)\) decreases from \(n=2k\) onward, and \(n^{k}\le c_{2k}\,2^{n}\) for all \(n\ge 2k\) : this is \(n^{k}=O(2^{n})\) , with \(C=c_{2k}\) and \(n_0=2k\) .
Suppose, for contradiction, that \(2^{n}\le Cn^{k}\) for all \(n\ge n_0\) . Applying what was just proved to the exponent \(k+1\) , there are \(C'\) and \(n_1\) with \(n^{k+1}\le C'2^{n}\) for \(n\ge n_1\) . For large \(n\) both hold, so \(n^{k+1}\le C'Cn^{k}\) , that is, \(n\le C'C\) . This fails for \(n>C'C\) . So \(2^{n}\) is not \(O(n^{k})\) .
(a) By induction \(n<2^{n}\) for all \(n\in\mathbb N\) , so \(\log_2 n<n\) for \(n\ge 1\) , which gives \(\log_2 n=O(n)\) . If \(n\le C\log_2 n\) held for all large \(n\) , then taking \(n=2^{m}\) would give \(2^{m}\le Cm\) for all large \(m\) , contradicting (b) with \(k=1\) .
(c) Example 3.2 showed \(2^{n}<n!\) for \(n\ge 4\) . For the other statement write, for \(n\ge 2\) ,
since the factors from \(\frac22\) to \(\frac{n-1}{2}\) are each at least \(1\) . The ratio exceeds every bound, so \(n!\) is not \(O(2^{n})\) .
The hierarchy can be extended by products: multiplying both sides of a comparison by the same positive function preserves it, so for instance \(n\log_2 n\) lies strictly between \(n\) and \(n^{2}\) . In increasing order of growth, the standard scale reads
Example 7.7: Witnesses for an upper and a lower bound
Claim. \(3n^{2}+5n+7=\Theta(n^{2})\) .
For the lower bound, \(3n^{2}+5n+7\ge 3n^{2}\) for all \(n\ge 0\) , so \(c=3\) and \(n_0=0\) are witnesses for \(\Omega(n^{2})\) . For the upper bound, when \(n\ge 1\) we have \(5n\le 5n^{2}\) and \(7\le 7n^{2}\) , so \(3n^{2}+5n+7\le 15n^{2}\) : the witnesses are \(C=15\) and \(n_0=1\) .
Witnesses are not unique, and a smaller constant can be bought with a larger starting point. The inequality \(3n^{2}+5n+7\le 4n^{2}\) is equivalent to \(n^{2}-5n-7\ge 0\) , which fails for \(n=6\) , where it reads \(-1\ge 0\) , and holds for \(n=7\) , where it reads \(7\ge 0\) , and for all larger \(n\) . So \(C=4\) and \(n_0=7\) also serve. No constant \(C\le 3\) can work for the upper bound, whatever \(n_0\) is, because the function always exceeds \(3n^{2}\) .
Constants in exponents are different. The function \(2^{n+1}\) is \(O(2^{n})\) , with \(C=2\) . But \(2^{2n}=4^{n}\) is not \(O(2^{n})\) : the ratio \(4^{n}/2^{n}=2^{n}\) exceeds every bound. A constant factor in front of a function does not change its growth class; a constant factor inside an exponent does.
Example 7.8: An induction that hides a growing constant
False claim. \(1+2+\dots+n=O(n)\) .
Argument. “Let \(S_n=1+2+\dots+n\) . Base case: \(S_1=1=O(1)\) . Step: assume \(S_k=O(k)\) . Then \(S_{k+1}=S_k+(k+1)=O(k)+O(k+1)=O(k+1)\) .”
Diagnosis. The claim is false: \(S_n=\frac{n(n+1)}{2}\) , and \(S_n/n=\frac{n+1}{2}\) exceeds every bound. The flaw is that “\(S_k=O(k)\) ” is not a statement about the number \(k\) . Big-O is a property of a whole function, asserting one constant \(C\) for all large \(n\) ; for a single value of \(k\) the phrase has no content, since any one number is at most some constant times \(k\) . The argument silently uses a new constant at each step. To do the induction honestly, fix \(C\) and let \(P(k)\) be the statement \(S_k\le Ck\) . The step would need \(S_k+(k+1)\le C(k+1)\) , and from the hypothesis one gets only \(S_{k+1}\le Ck+k+1\) , which is at most \(C(k+1)\) exactly when \(k+1\le C\) . For \(k\ge C\) the step fails, as it must.
Common mistake. Using asymptotic notation inside an induction hypothesis. Replace the notation by its definition, with the constant named and fixed before the induction begins, and prove the explicit inequality. If the constant has to change from one step to the next, the argument proves nothing.
7.5 Divide-and-conquer recurrences
Many efficient algorithms solve a problem of size \(n\) by splitting it into a few problems of size \(n/b\) , solving those in the same way, and combining the results. Their cost satisfies a recurrence in which \(n\) is divided, not decreased by one. Merge sort is the standard example: to sort a list of \(n\) numbers, sort each half and then merge the two sorted halves, which takes at most \(n\) comparisons. If \(T(n)\) bounds the cost for a list of length \(n\) , then
when \(n\) is a power of \(2\) .
Such a recurrence is solved by drawing its recursion tree. The root represents the original problem and is labelled with the cost \(n\) of its own splitting and combining. Its children represent the subproblems, each labelled with its own cost, and so on down to problems of size \(1\) . The total cost is the sum of all the labels, and the natural way to add them is level by level.
Example 7.9: Merge sort by its recursion tree
Let \(n=2^{k}\) . In the tree for \(T(n)=2T(n/2)+n\) , level \(j\) has \(2^{j}\) vertices, each a problem of size \(n/2^{j}\) with label \(n/2^{j}\) , for \(j=0,1,\dots,k\) . The sum of the labels on level \(j\) is \(2^{j}\cdot n/2^{j}=n\) : every level costs the same. There are \(k+1\) levels, counting the leaves, where each of the \(n\) problems of size \(1\) costs \(T(1)=1\) . So
The left tree in Figure 7.2 shows the case \(n=8\) : four levels, each summing to \(8\) , total \(32=8\cdot 3+8\) .
The tree is a way of finding the formula. To prove it, apply Proposition 7.2 to the sequence \(t_k=T(2^{k})\) , which satisfies \(t_k=2t_{k-1}+2^{k}\) and \(t_0=1\) . The formula \(2^{k}(k+1)\) gives \(1\) at \(k=0\) , and
so it satisfies the recurrence. Hence \(T(n)=n\log_2 n+n=\Theta(n\log_2 n)\) on powers of \(2\) . Compare sorting by adjacent swaps, which can need \(\frac{n(n-1)}{2}=\Theta(n^{2})\) swaps: for \(n=1024\) the two counts are \(11264\) and \(523776\) .
This answers the question that closed Chapter 6. A tree in which every vertex above the bottom has two children, down \(k\) levels, has \(2^{k}\) leaves; so the number of levels is the logarithm of the number of leaves, and that logarithm is the factor \(\log_2 n\) in the cost of merge sort.
The same computation handles a whole family of recurrences.
Theorem 7.11 (divide-and-conquer recurrences). Let \(a\ge 1\) and \(b\ge 2\) be integers and \(d\ge 0\) an integer. Suppose \(T(1)=1\) and \(T(n)=a\,T(n/b)+n^{d}\) for every \(n=b^{k}\) with \(k\ge 1\) . Then for \(n=b^{k}\) ,
and consequently, on powers of \(b\) : if \(a<b^{d}\) then \(T(n)=\Theta(n^{d})\) ; if \(a=b^{d}\) then \(T(n)=n^{d}(\log_b n+1)=\Theta(n^{d}\log n)\) ; and if \(a>b^{d}\) then \(T(n)=\Theta(a^{k})=\Theta(n^{\log_b a})\) .
Proof. In the recursion tree, level \(j\) has \(a^{j}\) vertices, each a problem of size \(n/b^{j}\) with label \((n/b^{j})^{d}\) , for \(0\le j\le k\) ; on the last level the problems have size \(1\) and cost \(T(1)=1=1^{d}\) . The sum of the labels on level \(j\) is \(a^{j}n^{d}/b^{jd}=n^{d}(a/b^{d})^{j}\) , and adding over the levels gives the formula. It is verified by Proposition 7.2 applied to \(t_k=T(b^{k})\) : the formula gives \(1\) at \(k=0\) , and \(a\,t_{k-1}+b^{kd}\) reproduces it, because multiplying the sum for \(k-1\) by \(a\) and by \((b^{k-1})^{d}\) shifts each term \(j\) to term \(j+1\) of the sum for \(k\) , and \(b^{kd}\) supplies the term \(j=0\) .
Put \(\rho=a/b^{d}\) . If \(\rho<1\) , the geometric sum lies between \(1\) and \(\frac{1}{1-\rho}\) by Theorem 7.3, so \(n^{d}\le T(n)\le\frac{1}{1-\rho}n^{d}\) . If \(\rho=1\) , every term of the sum is \(1\) and \(T(n)=n^{d}(k+1)\) with \(k=\log_b n\) . If \(\rho>1\) , Theorem 7.3 gives \(T(n)=n^{d}\frac{\rho^{k+1}-1}{\rho-1}\) , which lies between \(n^{d}\rho^{k}\) and \(\frac{\rho}{\rho-1}n^{d}\rho^{k}\) ; and \(n^{d}\rho^{k}=b^{kd}a^{k}/b^{kd}=a^{k}\) . Finally \(a^{k}=a^{\log_b n}=n^{\log_b a}\) , since both equal \(b^{(\log_b a)(\log_b n)}\) .
The three cases are three shapes of recursion tree. If \(a<b^{d}\) the level sums shrink geometrically and the root dominates. If \(a=b^{d}\) every level contributes equally. If \(a>b^{d}\) the level sums grow geometrically and the leaves dominate; there are \(a^{k}=n^{\log_b a}\) of them. The theorem is stated for powers of \(b\) and for the exact added term \(n^{d}\) ; the versions used in the analysis of algorithms extend it to all \(n\) and to added terms of order \(n^{d}\) , with the same three cases.
Example 7.10: One recurrence from each case
Root-dominated. \(T(n)=2T(n/2)+n^{2}\) : here \(a=2\) , \(b=2\) , \(d=2\) , and \(a<b^{d}=4\) . The ratio is \(\rho=\tfrac12\) , and for \(n=2^{k}\)
The values \(T(1),T(2),T(4),T(8)\) are \(1,6,28,120\) . So \(T(n)=\Theta(n^{2})\) : the work at the top level is already half of the total.
Balanced. \(T(n)=2T(n/2)+n\) : \(a=b^{d}=2\) . This is merge sort, \(T(n)=n\log_2 n+n\) , with values \(1,4,12,32\) .
Leaf-dominated. \(T(n)=3T(n/2)+n\) : \(a=3>b^{d}=2\) , and \(\rho=\tfrac32\) . For \(n=2^{k}\) ,
The values are \(1,5,19,65\) ; the right tree of Figure 7.2 shows \(T(4)=4+6+9=19\) . Since \(\log_2 3\approx 1.585\) , \(T(n)=\Theta(n^{1.585})\) . This recurrence describes a method of multiplying two \(n\) -digit numbers using three multiplications of half-length numbers in place of the obvious four; with four, \(a=4\) and the cost is \(\Theta(n^{2})\) . Saving one recursive call out of four changes the exponent.
A recurrence is the natural description of anything built from smaller copies of itself: a stack of discs, a string that extends a shorter string, a tree, a divided problem. With it the collection of methods is complete, and the remaining chapter is about choosing among them. A question to carry forward: the number of bit strings with no two consecutive ones was found by a recurrence; could it also have been counted directly, by choosing positions for the ones, and what would the two answers together prove?
Exercises
-
Compute the first six terms of the sequence given by \(a_0=1\) and \(a_n=2a_{n-1}+3\) , find a closed form by unrolling or by Theorem 7.4, and check the closed form against your six terms.
Answer
The terms are \(1,5,13,29,61,125\) . By Theorem 7.4 with \(c=2\) and \(d=3\) , \(a_n=2^{n}+3(2^{n}-1)=2^{n+2}-3\) , which gives \(4-3\) , \(8-3\) , \(16-3\) , \(32-3\) , \(64-3\) , \(128-3\) .
-
Solve the recurrence \(a_n=a_{n-1}+2n-1\) with \(a_0=0\) by unrolling, and identify the sum that appears with a result of Chapter 3.
Hint
Unrolling gives \(a_n=a_0+\sum_{i=1}^{n}(2i-1)\) , the sum of the first \(n\) odd numbers, which Example 3.1 evaluated.
-
Solve \(a_n=5a_{n-1}-6a_{n-2}\) with \(a_0=1\) and \(a_1=4\) , and verify your formula for \(n=2\) and \(n=3\) against the recurrence.
Solution
The characteristic equation is \(x^{2}=5x-6\) , that is, \((x-2)(x-3)=0\) , with distinct roots \(2\) and \(3\) . By Theorem 7.7(a), \(a_n=A\,2^{n}+B\,3^{n}\) . The initial conditions give \(A+B=1\) and \(2A+3B=4\) ; subtracting twice the first from the second, \(B=2\) , and then \(A=-1\) . Hence
\[ a_n=2\cdot 3^{n}-2^{n}. \]Verification: the recurrence gives \(a_2=5\cdot 4-6\cdot 1=14\) and \(a_3=5\cdot 14-6\cdot 4=46\) . The formula gives \(2\cdot 9-4=14\) and \(2\cdot 27-8=46\) . They agree, and since the formula satisfies the recurrence and the initial conditions by construction, Proposition 7.2 guarantees agreement for all \(n\) .
-
Solve \(a_n=6a_{n-1}-9a_{n-2}\) with \(a_0=2\) and \(a_1=3\) , and verify your formula for \(n=2\) and \(n=3\) .
Solution
The characteristic equation is \(x^{2}=6x-9\) , that is, \((x-3)^{2}=0\) , with the repeated root \(3\) . By Theorem 7.7(b), \(a_n=(A+Bn)3^{n}\) . From \(a_0=2\) we get \(A=2\) . From \(a_1=3\) we get \((2+B)\cdot 3=3\) , so \(B=-1\) . Hence
\[ a_n=(2-n)\,3^{n}. \]Verification: the recurrence gives \(a_2=6\cdot 3-9\cdot 2=0\) and \(a_3=6\cdot 0-9\cdot 3=-27\) . The formula gives \((2-2)\cdot 9=0\) and \((2-3)\cdot 27=-27\) . Notice that the sequence changes sign: the factor \(2-n\) is negative from \(n=3\) onward, so the terms are \(2,3,0,-27,-162\) .
-
Solve \(a_n=a_{n-1}+2a_{n-2}\) with \(a_0=2\) and \(a_1=1\) , and list the first six terms.
Answer
The characteristic equation \(x^{2}=x+2\) has roots \(2\) and \(-1\) , and the initial conditions give \(A=B=1\) : \(a_n=2^{n}+(-1)^{n}\) . The first six terms are \(2,1,5,7,17,31\) .
-
The Lucas numbers are defined by \(L_0=2\) , \(L_1=1\) , and \(L_n=L_{n-1}+L_{n-2}\) . Show that \(L_n=\varphi^{n}+\psi^{n}\) with \(\varphi\) and \(\psi\) as in Example 7.4, and deduce that \(F_{2n}=F_nL_n\) for all \(n\) .
Hint
By Lemma 7.6 the sequence \(\varphi^{n}+\psi^{n}\) satisfies the Fibonacci recurrence; check that its first two values are \(2\) and \(\varphi+\psi=1\) and apply Proposition 7.2. For the identity, multiply the two closed forms and use the difference of two squares.
-
Let \(a_0=0\) , \(a_1=1\) , and \(a_n=a_{n-1}-a_{n-2}\) . Compute the first twelve terms, prove that \(a_{n+3}=-a_n\) for all \(n\) , and deduce that the sequence repeats with period \(6\) . Explain why Theorem 7.7 does not apply as stated.
Solution
The first twelve terms are \(0,1,1,0,-1,-1,0,1,1,0,-1,-1\) .
For any \(n\ge 0\) , apply the recurrence twice:
\[ a_{n+3}=a_{n+2}-a_{n+1}=(a_{n+1}-a_n)-a_{n+1}=-a_n . \]Applying this identity twice gives \(a_{n+6}=-a_{n+3}=a_n\) , so the sequence repeats with period \(6\) . The period is not shorter: the block \(0,1,1,0,-1,-1\) is not a repetition of a block of length \(1\) , \(2\) , or \(3\) .
The characteristic equation is \(x^{2}=x-1\) , that is, \(x^{2}-x+1=0\) . Its discriminant is \(1-4=-3\) , which is negative, so it has no real root, and Theorem 7.7 was stated only for real roots. The roots are complex numbers whose sixth powers equal \(1\) , which is the algebraic reason for the period; a sequence with real characteristic roots cannot be periodic in this way unless a root is \(1\) or \(-1\) .
-
Use Proposition 7.2 to prove that the sequence defined by \(a_0=1\) and \(a_n=2a_{n-1}+3^{n}\) has the closed form \(a_n=3^{n+1}-2^{n+1}\) .
Solution
Let \(b_n=3^{n+1}-2^{n+1}\) . The recurrence \(a_n=2a_{n-1}+3^{n}\) is of order \(1\) , with the rule allowed to depend on \(n\) , so Proposition 7.2 applies: it suffices to check the initial condition and the recurrence for \(b_n\) .
Initial condition: \(b_0=3-2=1=a_0\) .
Recurrence: for \(n\ge 1\) ,
\[ 2b_{n-1}+3^{n}=2(3^{n}-2^{n})+3^{n}=3\cdot 3^{n}-2^{n+1}=3^{n+1}-2^{n+1}=b_n . \]Both conditions hold, so \(a_n=b_n\) for all \(n\) . The first terms \(1,5,19,65\) agree with direct computation from the recurrence. Guess and verify needs no theory about where the guess came from.
-
Let \(d_n\) be the number of ways to cover a \(2\times n\) board exactly with dominoes, each covering two adjacent squares. Derive a recurrence for \(d_n\) by considering how the last column is covered, state the initial conditions, express \(d_n\) as a Fibonacci number, and find \(d_{10}\) .
Solution
Consider the right-hand column of a \(2\times n\) board, for \(n\ge 2\) , in a covering. Its upper square is covered either by a vertical domino or by a horizontal one.
If it is covered by a vertical domino, that domino fills the last column, and the rest is a covering of a \(2\times(n-1)\) board: \(d_{n-1}\) ways. If it is covered by a horizontal domino, that domino occupies the upper squares of the last two columns. The lower square of the last column cannot then be covered by a vertical domino, so it too is covered by a horizontal domino, occupying the lower squares of the last two columns; the rest is a covering of a \(2\times(n-2)\) board: \(d_{n-2}\) ways. The cases are disjoint, so
\[ d_n=d_{n-1}+d_{n-2},\qquad d_1=1,\quad d_2=2 . \]Since \(d_1=F_2\) and \(d_2=F_3\) , Proposition 7.2 gives \(d_n=F_{n+1}\) . The values run \(1,2,3,5,8,13,21,34,55,89\) , so \(d_{10}=F_{11}=89\) .
-
Let \(t_n\) be the number of strings of length \(n\) over the alphabet \(\{a,b,c\}\) that do not contain two consecutive letters \(a\) . Find a recurrence of order two for \(t_n\) with its initial conditions, and compute \(t_5\) .
Answer
Sort by the last letter. If it is \(b\) or \(c\) , the first \(n-1\) letters form any valid string: \(2t_{n-1}\) . If it is \(a\) , the letter before it is \(b\) or \(c\) and the first \(n-2\) letters form any valid string: \(2t_{n-2}\) . So \(t_n=2t_{n-1}+2t_{n-2}\) with \(t_0=1\) and \(t_1=3\) , giving \(8,22,60\) and \(t_5=164\) .
-
In a variant of the Tower of Hanoi the pegs stand in a row, and a disc may be moved only between adjacent pegs. Describe a strategy that moves \(n\) discs from the first peg to the third, show that it takes \(R_n=3R_{n-1}+2\) moves, and solve the recurrence.
Hint
Move the top \(n-1\) discs from the first peg to the third, the largest to the middle, the \(n-1\) back to the first, the largest to the third, and the \(n-1\) to the third: three transfers of \(n-1\) discs and two moves of the largest. With \(R_0=0\) , Theorem 7.4 gives \(R_n=3^{n}-1\) .
-
The number \(D_n\) of derangements of \(n\) objects satisfies \(D_n=(n-1)(D_{n-1}+D_{n-2})\) for \(n\ge 2\) , with \(D_0=1\) and \(D_1=0\) . Check this against the values found in Chapter 5, compute \(D_6\) , and give a combinatorial reason for the recurrence by considering where the element \(1\) is sent.
Hint
The recurrence gives \(D_2=1\) , \(D_3=2\) , \(D_4=9\) , \(D_5=44\) , matching Chapter 5, and \(D_6=5\cdot(44+9)=265\) . For the reason: the element \(1\) goes to some \(j\ne 1\) , in \(n-1\) ways. Either \(j\) goes to \(1\) , and the other \(n-2\) elements are deranged among themselves; or \(j\) does not go to \(1\) , and then treating position \(1\) as the forbidden position for \(j\) gives a derangement of \(n-1\) elements.
-
Prove from Definition 7.8, naming your witnesses: (a) \(5n^{3}+2n+10=O(n^{3})\) ; (b) \(n^{3}\) is not \(O(n^{2})\) .
Solution
(a) Take \(C=17\) and \(n_0=1\) . For \(n\ge 1\) we have \(2n\le 2n^{3}\) and \(10\le 10n^{3}\) , so
\[ \lvert 5n^{3}+2n+10\rvert=5n^{3}+2n+10\le 5n^{3}+2n^{3}+10n^{3}=17n^{3}. \]This is the inequality required by Definition 7.8.
(b) Suppose, for contradiction, that \(n^{3}=O(n^{2})\) : there are \(C>0\) and \(n_0\) with \(n^{3}\le Cn^{2}\) for all \(n\ge n_0\) . Dividing by \(n^{2}\) , which is positive for \(n\ge 1\) , gives \(n\le C\) for all \(n\ge\max(n_0,1)\) . But any integer \(n\) larger than both \(C\) and \(n_0\) violates this. So no such \(C\) and \(n_0\) exist. The proof follows the negation of the definition: whatever witnesses are proposed, some large \(n\) defeats them.
-
Decide whether each statement is true, with a reason: (a) \(2^{n+3}=O(2^{n})\) ; (b) \(3^{n}=O(2^{n})\) ; (c) \((n+1)!=O(n!)\) ; (d) \(\log_2(n^{2})=O(\log_2 n)\) .
Answer
(a) True: \(2^{n+3}=8\cdot 2^{n}\) , so \(C=8\) . (b) False: \(3^{n}/2^{n}=(1+\tfrac12)^{n}\ge 1+\tfrac n2\) by Bernoulli’s inequality, which exceeds every bound. (c) False: \((n+1)!/n!=n+1\) exceeds every bound. (d) True: \(\log_2(n^{2})=2\log_2 n\) , so \(C=2\) .
-
Arrange the following functions in increasing order of growth: \(n\log_2 n\) , \(100n\) , \(2^{n}\) , \(n^{2}\) , \(n!\) , \(\log_2 n\) , \((1.01)^{n}\) , \(n^{3}\) . Then compare \((1.01)^{n}\) and \(n^{3}\) at \(n=1000\) and explain why this does not contradict your ordering.
Answer
\(\log_2 n\) , \(100n\) , \(n\log_2 n\) , \(n^{2}\) , \(n^{3}\) , \((1.01)^{n}\) , \(2^{n}\) , \(n!\) . At \(n=1000\) , \((1.01)^{1000}\approx 2.1\times 10^{4}\) while \(n^{3}=10^{9}\) , so the polynomial is still far larger. The ordering concerns all sufficiently large \(n\) : the exponential overtakes \(n^{3}\) only beyond \(n=2300\) and is larger ever after.
-
A student analyses \(T(n)=2T(n/2)+n\) as follows: “Assume \(T(n/2)\le c\cdot n/2\) . Then \(T(n)\le 2\cdot c\cdot n/2+n=cn+n=O(n)\) . So \(T(n)=O(n)\) by induction.” Find the error, and say what the induction would have had to show.
Solution
An induction must prove a statement \(P(n)\) with all its constants fixed in advance. Here the hypothesis is “\(T(m)\le c\,m\) for the smaller value \(m=n/2\) ”, so the statement to be proved for \(n\) is “\(T(n)\le c\,n\) ” with the same \(c\) . The student obtained \(T(n)\le cn+n=(c+1)n\) , which is weaker than \(T(n)\le cn\) and does not close the induction. Writing “\(=O(n)\) ” at that point conceals the fact that the constant has grown from \(c\) to \(c+1\) .
Followed honestly, the argument shows that the constant increases by \(1\) each time \(n\) doubles, so after \(k\) doublings it has grown by \(k=\log_2 n\) . That is the truth: \(T(n)=n\log_2 n+n\) by Example 7.9, and this function is not \(O(n)\) , since its ratio to \(n\) is \(\log_2 n+1\) . This is the error of Example 7.8 in a different setting.
-
Prove that the relation “\(f=\Theta(g)\) ” on the set of functions from \(\mathbb N\) to the positive reals is reflexive, symmetric, and transitive, and show by an example that the relation “\(f=O(g)\) ” is not symmetric.
Hint
For transitivity use Proposition 7.9(a) for the upper bounds and the analogous argument for the lower bounds. For symmetry, an inequality \(f(n)\le Cg(n)\) can be rewritten as \(g(n)\ge\frac1C f(n)\) . For the example, compare \(n\) and \(n^{2}\) .
-
Let \(T(1)=1\) and \(T(n)=3T(n/3)+n\) for \(n=3^{k}\) . Describe the levels of the recursion tree, find the closed form, verify it with Proposition 7.2, and state which case of Theorem 7.11 this is.
Solution
Let \(n=3^{k}\) . In the recursion tree, level \(j\) has \(3^{j}\) vertices, each a problem of size \(n/3^{j}\) with label \(n/3^{j}\) , for \(j=0,\dots,k\) ; on the last level the labels are \(T(1)=1\) . Every level sums to \(3^{j}\cdot n/3^{j}=n\) , and there are \(k+1\) levels, so
\[ T(n)=n(k+1)=n\log_3 n+n . \]Verification by Proposition 7.2 for \(t_k=T(3^{k})\) , which satisfies \(t_0=1\) and \(t_k=3t_{k-1}+3^{k}\) : the formula \(3^{k}(k+1)\) gives \(1\) at \(k=0\) , and \(3\cdot 3^{k-1}k+3^{k}=3^{k}(k+1)\) . For instance \(T(3)=6\) and \(T(9)=27\) .
In Theorem 7.11 this is \(a=3\) , \(b=3\) , \(d=1\) , so \(a=b^{d}\) : the balanced case, with \(T(n)=\Theta(n\log n)\) .
-
Binary search on a sorted list of length \(n\) compares the target with the middle entry and continues in one half. Its cost satisfies \(T(n)=T(n/2)+1\) with \(T(1)=1\) . Find \(T(n)\) for \(n=2^{k}\) , and compare the number of comparisons for a list of length \(2^{20}\) with the number needed by a search that examines every entry.
Answer
\(T(2^{k})=k+1\) , that is, \(T(n)=\log_2 n+1\) . For a list of length \(2^{20}=1048576\) binary search uses \(21\) comparisons, against up to \(1048576\) for a search that examines every entry.
-
For each recurrence, with \(T(1)=1\) and \(n\) a power of \(2\) , state the case of Theorem 7.11 and the resulting growth rate: (a) \(T(n)=4T(n/2)+n\) ; (b) \(T(n)=4T(n/2)+n^{2}\) ; (c) \(T(n)=4T(n/2)+n^{3}\) ; (d) \(T(n)=T(n/2)+n\) ; (e) \(T(n)=7T(n/2)+n^{2}\) .
Answer
(a) \(a=4>b^{d}=2\) : leaf-dominated, \(\Theta(n^{2})\) . (b) \(a=4=b^{d}\) : balanced, \(\Theta(n^{2}\log n)\) . (c) \(a=4<b^{d}=8\) : root-dominated, \(\Theta(n^{3})\) . (d) \(a=1<b^{d}=2\) : root-dominated, \(\Theta(n)\) . (e) \(a=7>b^{d}=4\) : leaf-dominated, \(\Theta(n^{\log_2 7})\) , and \(\log_2 7\approx 2.81\) .
-
Solve \(T(n)=4T(n/2)+n\) with \(T(1)=1\) exactly for \(n=2^{k}\) by adding the levels of the recursion tree, and verify your closed form for \(n=1,2,4,8\) .
Solution
Let \(n=2^{k}\) . Level \(j\) of the recursion tree has \(4^{j}\) vertices, each a problem of size \(n/2^{j}\) with label \(n/2^{j}\) , for \(j=0,\dots,k\) , the last level consisting of \(4^{k}\) problems of size \(1\) with label \(T(1)=1\) . The sum on level \(j\) is \(4^{j}\cdot n/2^{j}=n2^{j}\) . By Theorem 7.3,
\[ T(n)=n\sum_{j=0}^{k}2^{j}=n(2^{k+1}-1)=n(2n-1)=2n^{2}-n . \]Verification: the recurrence gives \(T(1)=1\) , \(T(2)=4\cdot 1+2=6\) , \(T(4)=4\cdot 6+4=28\) , \(T(8)=4\cdot 28+8=120\) , and the formula gives \(2-1\) , \(8-2\) , \(32-4\) , \(128-8\) , the same four numbers. The level sums double from each level to the next, so the leaves contribute \(n\cdot 2^{k}=n^{2}\) , about half the total: this is the leaf-dominated case of Theorem 7.11.
-
With \(T(1)=1\) , compute \(T(1024)\) exactly for \(T(n)=4T(n/2)+n\) and for \(T(n)=3T(n/2)+n\) using the closed forms from this chapter, and find the ratio of the two costs to two significant figures.
Answer
For \(T(n)=4T(n/2)+n\) : \(2\cdot 1024^{2}-1024=2096128\) . For \(T(n)=3T(n/2)+n\) : \(3\cdot 3^{10}-2\cdot 1024=177147-2048=175099\) . The ratio is about \(12\) .