EECS 3101 York University Instructor: Andy Mirzaian
RECURRENCE RELATIONS
In this lecture note we study some basic recurrence relations. These equations arise in the analysis of algorithms, among other things. We consider the following:
1. Divide-&-Conquer Recurrences and the Master Theorem. 2. Full History Recurrences.
3. The Guess-then-Verify Technique.
4. The Variable Substitution Method.
There are other method, such as the recursion tree and the generating function methods, that we will not discuss in this lecture note.
1. THE DIVIDE-AND-CONQUER RECURRENCES
Let α and β be positive integers both greater than one. Let us assume that we can divide a problem of size n into α subproblems, each of the same type, each of size n/β . Termination of the algorithm is guaranteed because β is greater than one, i.e. each of the subproblems is smaller than the original. These subproblems are solved recursively, and then their solutions are com- bined to get the solution of the original problem of size n. Let us assume the time needed to divide the problem into α subproblems plus combine together their solutions is f (n), called the driving function. Of course, if the problem is sufficiently small, e.g., n≤1, then we solve it directly without recursion. Let us assume for n≤1 it takes a constant amount of time, say γ steps, to solve the problem. If we denote the time complexity of our algorithm by T (n), then we have:
αT(β)+f(n) ∀n>1
T(n) =
n
γ ∀n≤1
(I)
Example 1: Consider the merge-sort algorithm. For simplicity, let n be a power of two. The input to the merge-sort is a list of n keys which are to be sorted into increasing order. Merge-sort splits the original list at the midpoint into two lists each with n/2 keys, sorts each of these two new lists recursively using merge-sort, and then merges these two sorted lists into a single sorted list containing all n keys in at most n time steps. Thus, the running time T(n) for merge-sort is expressed by equation (I), where α = 2, β = 2 and f (n) = n, and you may assume γ = 1.
We solve recurrence (I) for T(n) in two steps. In the first step we solve the somewhat simpler homogeneous recurrence:
-2-
α h ( β ) ∀ n > 1
1 ∀n≤1
n
h(n) =
(II)
(This can be interpreted as if we have, momentarily, set the driving function to zero, i.e. the dividing and combining steps take no time, only the recursive calls remain!)
We can solve (II) for h(n) rather easily by repeated substitution (also called the iteration method). Let k=logβ n (thus, βk−1
From above we have:
We have solved (II) and completed the first step. In the second step let us define:
Q(n) = T (n) / h(n) (V)
That is, T (n) = Q(n) ⋅ h(n). Substituting this in (I) we get:
n2n knk
h(n)=α h( )=α h( )=…=α h( )=α (III)
ββ2βk
h(n) = α k = α logβ n = Θ(α logβ n) = Θ(nlogβ α ) † (IV)
Q(n)⋅h(n) = αQ(β)⋅h(β)+f(n) ∀n>1
nn γ ∀n≤1
Using (II), we can simplify the above equation ( divide by h(n) ) to (VI) below. (This is the rea- son why we solved (II) first.)
Q(n) = (VI) γ ∀n≤1
For simplicity let’s first assume n = β k , i.e., k = logβ n. We can solve (VI) again by iterated sub-
n f(n) Q(β)+h(n) ∀n>1
stitution.
Q(n)=Q(βk) =Q(βk−1)+ f(βk)
h(βk) =Q(βk−2)+ f(βk−1)+ f(βk)
h(β k−1) h(β k) † By taking log from each side, show that xi logy z = zi logy x (i.e, x & z swapped).
=…
i=1 h(βi) Since Q(β 0) = Q(1) = γ , and from (IV) h(β i) = β i logβ α
= α i logβ β
= α i , we have:
Q(n)=γ +
Since T (n) = Q(n) ⋅ h(n), from (IV) and (VII) we get:
(VII)
(VIII)
k f(βi) =Q(β0)+Σ
k
Σ f(βi)
-3-
i=1
αi
k
Σ f(βi)
T(n)=Θ nlogβα γ+ . i=1αi
Exercise 1: What if n is not βk, i.e, log n is not an integer? Recall that k = log n . If f(.) ββ
satisfies f (Θ(m)) = Θ( f (m)) ∀m, we say f (. ) is a faithful function. For instance all polynomials are faithful. Starting with Q(n) and using the iterated substitution again, prove that the asymp- totic solution (VIII) is still valid when f is a faithful function.
The solution to our original recurrence relation (I) is (VIII). Let us consider some examples.
Example 1 (revisited) :
In (I) assume α = 2, β = 2, γ = 1 and f (n) = n. That is
T(n) = 2
1 ∀n≤1
Therefore, T (n) = Θ( n lg n ).
n
2 T ( ) + n ∀ n > 1
The solution, from (VIII), is:
T(n)=Θ nlog2 2 1+Σ =Θ(n(1+Σ1))=Θ(n(1+k))
k2i k i=1 2i i=1
= Θ(n (1 + lg n ))
There is a summation term in (VIII). We need to know ways of obtaining closed form formulas for such summations, although it turned out to be rather simple in the above example.
Power summation:
m
Sj(m)=1j +2j +3j +…+mj = Σij. Here are a few cases:
i=1 S (m)=m(m+1)/2=Θ(m2)
1
S (m)=m(m+1)(2m+1)/6=Θ(m3) 2
S (m)=(S (m))2 =Θ(m4) 31
In fact, using integration to bound the summation, it can be shown that S j(m) = Θ(m j+1) for any constant j ≥ 0.
Hm = Θ( lg m). Example 2:
Consider the following recurrence:
-4-
111 Harmonic numbers: The m-th harmonic number is Hm =1 + + +… + .
23m
An approximation formula (see, for example, Knuth, vol 1, or chapter 3 of [CLR]) says Hm ∼=ln m ∼=0. 7 lg m, where ln is the natural logarithm with the base e = 2. 7182… Thus,
4 T ( ) + n2 lg n ∀n >1
n
2
1 ∀n≤1
(2i)2 lg(2i) =Θ
T(n) =
T(n)=Θ
=Θ(n2(1+(lg2 n))) Therefore, T (n) = Θ( n2 lg2 n ).
The solution is
i=1 4i i=1
k 1+Σ
k 1+Σlg(2i)
n2
=Θ n2 1+ i =Θ(n2(1+S(k)))=Θ(n2(1+k2))
nlog2 4 Σ
k
i=1
1
Example 3:
Consider the following recurrence
4T( )+ ∀n>1
The solution is
Therefore, T (n) = Θ( n2 lg lg n ).
T(n) =
n n2
2 lg n 1 ∀n≤1
Σ T(n)=Θ nlog24 1+
i2i k (2) /lg(2)
i=1 4i k1
Σ = Θ n2 1 + = Θ n2 (1 + H )
= Θ(n2 (1 + lg k) )
k
i=1i
= Θ(n2 (1 + lg lg n ))
Polynomial Driving Function – The Master Theorem
Often the driving function is some polynomial in n, i.e. f (n) = Θ(nd), say, f (n) = cnd for some constants c > 0 and d ≥ 0. In other words, the recurrence is:
In this case we can considerably simplify the solution given in (VIII) as follows:
Θ(h(n)) = Θ( nlogβ α ) T(n) = Θ(f(n)) = Θ(nd)
Θ( f (n) lg n) = Θ( nd lg n )
if α > β d if α < βd if α = β d
[ case 1 ]
[case 2] (IX) [ case 3 ]
-5-
αT( )+cnd ∀n>1
n
T(n) =
β
γ ∀n≤1
Note that the asymptotic solution above does not depend on the two constants c and γ .
A sketch of the proof is as follows. Use equation (VIII) with f (n) = cnd . The term of the sum-
mation can be simplified to
Let x = βd/α. The above summation depends on the value of x. If x =1, that is case 3 above, then the above summation simplifies to ck = Θ(lg n). On the other hand, if x ≠ 1, then the above summation forms a geometric series. If x < 1, that is case 1, then the geometric summation con- verges, and hence is no more than a constant. Thus, the above summation simplifies to Θ(1). If x > 1, that is case 2, then the geometric summation can be simplified by noting that
k f(βi) kβdi Σαi =cΣα
Σk i=1
x x−1
⋅(xk −1)=Θ(xk)=Θ
βkd nd
xi =
αk
=Θ . h(n)
i=1 i=1
The case of polynomial driving function occurs quite frequently in practice. Therefore, the above simple solution is worthwhile to remember. For a more general version and its proof, see “The Master Theorem” in [CLR, page 62].
Exercise 2: Give a complete proof of the above solution for the case of the polynomial driving function by filling in the details in the above proof sketch.
Example 1 (revisited again): We have α =β =2 and f(n)=nd with d =1. Comparing α and β d , we see that β d = 2 = α . Thus, case 3 above holds, i.e. T (n) = Θ( nd lg n ) = Θ( n lg n ), as we expected.
Exercise 3: Generalize the above Master Theorem for the case f (n) = Θ(nd lgt n) for some constants d , t ≥ 0. Show that essentially the same solution holds as in (IX). That is,
Θ(h(n)) T(n) = Θ(f(n))
Θ( f (n) lg n)
if α > βd if α < βd if α = β d
-6-
Hint: use integration to obtain tight bounds on the summations involved in the proof.
2. FULL HISTORY RECURRENCES
A second type of recurrence relation which usually arises in some average-case analyses has the following typical form:
n−1
T(n)=ΣT(i)+ f(n) ∀n≥0. (X)
i=0
That is, T(0) = f (0), T(1) = T(0) + f (1), T(2) = T(0) + T(1) + f (2), and so on. This recurrence appears to be more complicated, since not just one but many terms of "T" appear on the right hand side of the equation.
For n > 0 we may substitute n −1 for n and get:
n−2
T(n−1)=ΣT(i)+ f(n−1). (XI)
i=0
Subtract (XI) from (X) to get:
T(n)−T(n−1)=T(n−1)+ f(n)− f(n−1).
We conclude:
2 T ( n − 1 ) + [ f ( n ) − f ( n − 1 ) ] ∀ n ≥ 1
T(n) = (XII)
f(0) for n=0
Now the term “T ” appears only once on the right hand side. We can now solve equation (XII) by
repeated substitution. The details are left to the reader.
Exercise 4: Solve the following recurrences. Recurrence (b) arises in the average-case analysis of the QuickSelect algorithm, and recurrence (c) arises in the average-case analysis of the Quick- Sort algorithm.
nΣ−1
i=0 1 nΣ−1 n i=0 2 nΣ−1 n i=0
T(n) = 2
T(i)+1 (a)
T(n) =
T(n) =
T(i) + n (b) T(i) + n (c)
i=0 Subtract (c2) from (c1) and simplify the terms to get:
-7-
n−1
T(n) = Σi⋅T(i)+n (d)
i=0
Example 4: Let us solve Exercise 4(c) †. First multiply the equation by n to get:
n−1
nT(n) = 2ΣT(i)+n2 ∀n≥0. (c1)
i=0 Now substitute n − 1 for n in (c1) to get:
n−2 (n−1)T(n−1) = 2ΣT(i)+(n−1)2
∀n≥1. (c2) nT(n) = (n+1)T(n−1)+2n−1 ∀n≥1. (c3)
Divide (c3) by n(n +1) to get:
Observe that the first term on the right hand side is similar to the term on the left hand side, and
T(n) T(n −1) 2n −1
= + ∀n≥1 (c4)
note also that:
Using the above observation, define:
2n−1 3 1
=− (c5)
n +1 n n(n +1)
n(n +1) n +1 n
Q(n) = T(n)/(n +1) ∀n ≥ 0 (c6)
Substitute (c5) and (c6) in (c4) to get:
Q(n−1)+3−1 ∀n≥1
Q(n) = n+1 n (c7)
0 for n = 0
Now use repeated substitution to solve (c7): 31313131
Q(n)=(
− )+( − )+( n+1 n n n−1
−
n−1 n−2
)+…+( − )+Q(0) (c8) 2 1
n+11 n1 =3Σ−Σ =2Hn−
3n i=2i i=1i n+1
Finally, from (c6) and (c8) we obtain:
T(n) = 2(n+1)Hn −3n (c9)
Since Hn = ln n + O(1) = Θ(lg n), we conclude T(n) = Θ(n lg n).
T(y) dy + x. Try to solve this inte- gral equation similar to the (discrete) method taken for the solution of Exercise 4(c).
† Note the resemblance to the integral equation T(x) =
2 ∫x
x0
-8-
3. THE GUESS-THEN-VERIFY TECHNIQUE
One method that has proven to be powerful if used effectively is the guess-then-verify method. To illustrate the method let us start with a simple example.
Example 5: Consider the recurrence:
T(n) = T(n−1)+n ifn≥1
0 if n = 0
This recurrence could easily be solved by the iterated substitution method. But let us guess a
solution, then verify its correctness by induction on n.
First Guess: Let us guess T(n) = O(n). So, we want to verify that T(n) ≤ an for all n ≥ no, for
some constants a and no to be determined. Let us “verify” this guess by induction on n.
The base case (n = 0) is T(0) = 0 ≤ a⋅0, which is valid. For the inductive step (n ≥1), assume the induction hypothesis T (i) ≤ a ⋅ i for all i < n, then try to verify that T (n) ≤ an. From the recurrence and the induction hypothesis for i=n−1, we have T(n)=T(n−1)+n≤a(n−1)+n=(a+1)n−a. If (a+1)n−a≤an, we would conclude T (n) ≤ an and complete the verification. But, there is no positive constant a that would satisfy (a +1)n − a ≤ an for all sufficiently large n.
The conclusion is that our "guess" was wrong! We have to make a new guess and verify it. Should we guess low or high? We should guess high. Why? Because, in the last crucial inequal- ity that we needed to be satisfied (i.e., (a +1)n − a ≤ an) we see that our guess, i.e., the right hand side of the inequality is too low compared to the left hand side. This would be the case even if we added some lower order terms to our guess, like T (n) ≤ an + o(n). Here is the key idea: in the last crucial inequality, the dominating terms on each side should be balanced. Once we have figured out the dominating term, we can carry out the same guess-then-verify idea in determining the lower order terms. After gaining some experience in the use of the method, we can become more efficient in guessing the right solution quickly. (See also page 55 of [CLR] on "making a good guess".) Let us carry on our guessing game for now!
Second Guess: Let us guess T (n) = Ω(n3). So, let’s verify that T (n) ≥ an3. The basis goes through fine again. In the inductive part we get T(n) = T(n −1) + n ≥ a(n −1)3 + n ≥ an3. the last crucial inequality is not balanced and shows our guess is too high. This would be the case even if we subtracted some lower order terms to our guess, like T (n) ≥ an3 − o(n3).
Third Guess: So, so far, we know that T(n) is strictly above O(n), and strictly below Ω(n3). Not to drag the discussion too long, let us guess that T(n)=O(n2). We will verify that T(n) ≤ an2 + bn + c, for some constants a, b and c to be determined. The basis for n = 0 gives us T(0)=0≤a⋅02+b⋅0+c. This is satisfied if c≥0. The inductive part gives us T(n)=T(n−1)+n ≤ a(n−1)2 +b(n−1)+c = an2 +(1+b−2a)n+(a−b+c). It would be sufficient to have the latter quantity to be ≤an2+bn+c. That is we want an2 + (1 + b − 2a)n + (a − b + c) ≤ an2 + bn + c. At last, the dominating terms on both sides of this last crucial inequality balance up. For the inequality to hold for all n ≥ 1, it is sufficient to match the left and right hand side term by term, that is, to have (1 + b − 2a) ≤ b (i.e., a ≥ 1/2) and (a − b + c) ≤ c (i.e., b ≥ a). So, all the conditions we have on the constants a, b and c from the
-9-
basis and the inductive step are c ≥ 0 and b ≥ a ≥ 1/2. We see the choice a = b = 1/2 and c = 0 works. That is, we have verified that T (n) ≤ (n2 + n)/2 for all n ≥ 0. This proves that T(n)=O(n2). In fact, it should now be easy to see from the verification steps that T (n) = (n2 + n)/2. Hence, T (n) = Θ(n2).
Exercise 5: Solve the recurrence T(n) = T(n −1) + n2, for n ≥1, and and T(0) = 0, using the guess-then-verify technique. Keep the unsuccessful trials as scratch work and just give the final successful trial.
Example 6: (Problem 4-4(b), page 73 of [CLR]) Consider the recurrence T(n) = 3T(n/3 + 5) + n/2
For this recurrence to be well defined, we must have n/3 + 5 < n, i.e., n ≥ 8. So we assume the boundary condition T (n) = c for all n < 8, where c is some positive constant.
We will use the guess-then-verify technique. As a first approximation, we notice that for asymp- totically large n, the recurrence is close to T ′(n) = 3T ′(n/3) + Θ(n). Using the Master Theorem, we know the latter recurrence has the solution T ′(n) = Θ(n lg n). Going back to the original recurrence, we now prove the following.
Claim: T(n)=Θ(nlgn).
Proof: We need to show the following two facts: (i) T(n) = O(n lg n), and
(ii) T(n)=Ω(nlgn).
Here we only show the proof of (i). Part (ii) can also be proved by the guess-then-verify method. Another way to prove part (ii) is to notice that T(n) ≥ T′(n), then apply the lower bound on T′(n) to T (n).
Proof of (i):
We will show that T (n) ≤ (an − b) lg n, say, for all n ≥ 10, for some suitable constants a and b. We will prove this by induction on the number of applications of the recurrence (coarsely speak- ing, on n).
We first notice that
n + 5 ≤ n ∀ n ≥ 30 (6.1) 32
Basis (10 ≤ n < 30):
Here we can make T (n) ≤ (an − b) lg n for all n in the range 10 ≤ n < 30, if we choose the con- stant a large enough compared to constant b. More specifically, we must have
T (n) lg n
for 10≤n≤30. (6.2) Note that in the above inequality, for the bounded range 10 ≤ n ≤ 30, the values of T (n) and
b≤an− hence T (n) / lg n are bounded.
Induction Step (n ≥ 30):
T(n) = 3T(n/3 + 5) + n/2
stants a and b:
a.
15 T(n)
-10-
≤ 3( a(n/3 + 5) − b ) lg (n/3 + 5) + n/2 {by the induction hyp.} ≤ 3( a(n/3 + 5) − b ) lg n/2 + n/2 {by (6.1)}
= (an − b) lg n − [ (a − 1/2)n − b] − (2b − 15a) lg n/2
≤ (an − b) lg n .
The last inequality will hold if [(a − 1/2)n − b] ≥ 0 and
(2b − 15a)lg n/2 ≥ 0.
The first inequality is implied by a ≥ 1/2 and b ≤ 30(a − 1/2) (which is ≤ (a − 1/2)n). The second
15
inequality is satisfied if b ≥
From the basis and the induction step, we have the following conditions for the existence of con-
2
1 a≥ ,
2
(6.3)
(6.4)
(6.5)
a ≤ b ≤ min ( an − , 30a − 15 ) . 10≤n≤30 lg n
2
In eq. (6.4) for such a constant b to exist, we must have
15 T(n)
2
a ≤ min ( an − . 30a − 15 ) . 10≤n≤30 lg n
We can certainly choose a large enough to simultaneously satisfy eqs. (6.3) and (6.5), since the coefficient of a on the left hand side of eq. (6.5) is 7. 5, while on the right hand side, the coeffi- cient of a is larger (it is at least 10). This completes the proof.
4. THE VARIABLE SUBSTITUTION METHOD
Consider the recurrence
T(n) = 2
0 ∀n≤1
Let us change the variable n to a new variable k = lg n (i.e., n = 2k ). Now the recurrence becomes T(2k) = T(2k−1) + k, for k > 0. T(2k) is a function of k; let’s rename it as S(k). So, the recurrence is
S ( k ) = S ( k − 1 ) + k ∀ k > 0 0 ∀k≤0
Now with a simple iteration method, we see the solution is S(k) = k + (k −1) + (k − 2) + … + 1 = Θ(k2). Thus, T(n) = T(2k) = S(k) = Θ(k2) = Θ(lg2n).
n
T( )+lg n ∀n>1
Exercise 9:
The exact recurrence for the worst-case number of comparisons in MergeSort is:
T(n)+T(n)+n−1 for n>1 T(n) = 2 2
Σa=na− in
Σ i=1 i=1
Σ i=2
(c)
ΣΣ
i=1 nn
1 i=1j=1 i+j
-11-
Example 6 (again): Consider the recurrence
T (n) = 3T (n/3 + 5) + n/2 .
To simplify this recurrence using the variable substitution method, let’s change the variable n to k such that n = g(k) and g(k −1) = n/3 + 5 = g(k)/3 + 5. Now rename T(g(k)), a function of k, as S(k). We now have the following two recurrences to solve:
g(k)=3g(k−1)−15and (6.1) 1
g(k) (6.2)
You should also carefully set up their boundary conditions. First solve eq. (6.1) to obtain g(k) as a function of k. Then plug g(k) in eq. (6.2) and solve it for S(k). We now have a solution for S(k)=T(g(k)) as a function of k. We need the functional inverse k=g−1(n) to obtain T(n) = S(k) = S(g−1(n)) as a function of n. We leave the details as exercise for the reader.
Exercise 6: Show the following identities hold for any real number series (ai): nn−1 n
S(k) = 3S(k −1) +
2
i(a −a)=(n+1)a−a− i(a−a).
i+1i n1
[Note: this is the discrete version of the integration by parts: ∫ f (x)dx = xf (x) − ∫ x df (x).]
Exercise 7: Using exercise 6, derive closed form formulas for:
n
(a) Σ lg i
i=1
n ni1 (b) ΣHi=ΣΣj
i=1 j=1
i i−1
Consider the recurrence T (n) = T (α n) + T (β n) + n, where 0 < α < 1 and 0 < β
are constants. Show that T (n) = Θ(n) if α + β < 1, and T (n) = Θ(n lg n) if α + β = 1. What if α + β > 1?
Exercise 8:
< 1
0 for n≤1
Using induction on n, verify the exact solution to the recurrence is: T (n) = n lg n − 2 lg n + 1 .
-12-
After giving it a good try, compare your solution to Parberry’s article "Everything you wanted to know about the running time of mergesort but were afraid to ask" in ACM SIGACT News, 29(2), June 1998, pp. 50-57.
Exercise 10: Solve T (n) = T (n/2 + 5) + c, where c > 0 is some constant.
[Hint: substitute n = g(k), where g(k −1) = n/2 + 5, i.e., g(k) = 2g(k −1) − 10, and g(0) = 11. Solve for g(k) and substitute it in the original recurrence.]
Exercise 11: Solve T (n) = T (n/2 + √n) + n by the guess-then-verify technique. Assume the usual boundary condition T (O(1)) = O(1).
Exercise 12: Let T (n) = max { T (k) + T (n − k) + k } for n > 2, and T (n) = 1 for n ≤ 2. Show 1≤k≤n/2
that T(n) = O(n lg n).
Exercise 13: Solve the recurrence T(n) = (T(n −1))2 for n > 0, and T(0) = 2.
[Hint: substitute g(n) = lg (T (n)).]
Exercise 14: Solve the recurrence T(n) = T(lgn) +1 for n>2, and T(n) = 2 for n ≤ 2.