4.
Recurrences
Chapter 4. Recurrences (cont.)
Approaches to solving recurrences. When an algorithm contains a recursive call to itself, its running time can often be described by a recurrence. A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs. E.g., the running time T (n) of the merge-sort algorithm can be expressed in a recurrence.
Substitution method:
Guess a bound, and prove that the guess is correct using mathematical induction.
Iteration method:
Convert the recurrence into a summation, and then use the techniques of bounding summations to solve the recurrence.
T (n) =
(1),
T (dn=2e) + T (n=2) + (n), otherwise
if n = 1,
Apply a standard result:
Such as the Master Theorem.
COMP3600/6466: Lecture 5
2011
COMP3600/6466: Lecture 5
2011
4.1 Substitution Method
4.1 Substitution Method (continued)
Special consideration when applying substitution method.
The substitution method consists of two steps.
1. Making a good guess:
Step 1. Guess the form of the solution. Step 2. Use mathematical induction to nd the constants (boundary conditions),
and show that the guess is correct. Note that a good guess is vital when applying this method. If the initial guess is wrong, the guess needs to be adjusted later.
T (n) = 2T (n=3 + 105) + n T (n) = T (n=2) + T (dn=2e) + 5 T (n) = 2T (n=2) + n T (n) = 2T ( n) + log n
2. Subtleties:
3. Avoiding pitfalls:
4. Changing variables:
COMP3600/6466: Lecture 5
2011
COMP3600/6466: Lecture 5
2011
4.1 Substitution Method (continued)
Making a good guess: T (n) = 2T (n=3 + 105) + n
Proof: Let T (n) = cn log n for all n
4.1 Substitution Method (continued)
To meet the above inequality, we require Thus, nH 0
! n0, Assume that for some constant c > 0, and all nH ! n0, we have
T (nH)
for any n0 we have
On the other hand, we require (2c 3)n log n + 210c log n + n i.e., 630 3
105 3 . 2
n=3 + 105
n,
cnH log nH,
cn log n,
< nH < n (this is the induction hypothesis.) Then, applying the recurrence,
T (n) = 2T (n=3 + 105) + n 2c(n=3 + 105) log(n=3 + 105) + n (2c=3)n log n + 210c log n + n cn log n
COMP3600/6466: Lecture 5 2011 5
We set c = 1 and nHH = 2630, then the above inequality holds. 0 Thus, there is a constant c = 1 and n0 = 2630 such that for any n
c log n
1,
! n0,
6
T (n)
COMP3600/6466: Lecture 5
cn log n.
2011
4.1 Substitution Method (continued)
Subtleties: T (n) = T (n=2) + T (dn=2e) + 5
Proof: We use mathematical induction, starting with an educated guess that the answer might be T (n)
4.1 Substitution Method (continued)
So, instead, we adjust our guess to T (nH) we have
cnH b and b > 0 is a constant. Then,
cn.
Assume that for some constant c
> 0 and all nH ! n0, we have
T (nH) cnH,
T (n) = T (n=2) + T (dn=2e) + 5 cn=2n b + cdn=2e b + 5 = cn 2b + 5 cn,
We thus have
for n0 have
< nH < n. (This is the induction hypothesis.) Then, applying the recurrence, we
cn 2b + 5
Therefore, b
cn,
T (n) = T (n=2) + T (dn=2e) + 5 cn=2 + cdn=2e + 5 = cn + 5
COMP3600/6466: Lecture 5 2011 7
! 5=2 = 2. 5. Now for any n ! n0 = 2, there is a constant c = 1 such that T (n) cn 2. 5
2011 8
holds, i.e., T (n) = O(n). COMP3600/6466: Lecture 5
4.1 Substitution Method (continued)
4.1 Substitution Method (continued)
Changing variables: p T (n) = 2T ( n) + log n
Avoiding pitfalls: T (n) = 2T (n=2) + n
Proof: If we assume that T (nH)
cnH for any nH < n, then we have
Let n = 2m, then log n = m and
Proof: We rst assume that n is the power of 2.
T (n)
= 2T ( n 2 ) + n
= 2cn=2 + n
pn = 2m=2. p Let S(m) = T (n), then S(m=2) = T ( n). Thus, we have S(m) = 2S(m=2) + m,
The solution of the above recurrence is S(m) = (m log m). We also know m = log n, then T (n) = (log n log log n). If n is not the power of 2, then 2m
(1)
cn + n = (c + 1)n = O(n), (W RONG!)
n < nHH = 2m+1, while T (nHH) = (log n log log n).
2011 10
T (n)
COMP3600/6466: Lecture 5 2011 9 COMP3600/6466: Lecture 5
4.2 Iteration Method
The iteration method does not require guessing the answer, but it may require more algebraic knowledge than the substitution method. The idea is to expand (iterate) the recurrence and express it as a summation of terms, depending only on n and the initial conditions. For example, consider
4.2 Iteration Method (continued)
The recursion tree can be used to help nd the solution to a recurrence.
T (n) = 3T (n=4) + cn2
T (n) = 3T (n=4) + cn2.
A useful property: For integers a, b
x=a j x k
b
=
ab
! 1, and any x, dx=ae = l x m . and
b ab
(Cormen, p89)
Example:
n=4=4 = n=16
2011 11 COMP3600/6466: Lecture 5
COMP3600/6466: Lecture 5
2011
12
4.2 Iteration Method (continued)
T (n) = T (n=3) + T (2n=3) + cn (Cormen, p91)
(Cormen, p89)
COMP3600/6466: Lecture 5
2011
13
COMP3600/6466: Lecture 5
2011
14
4.3 Master theorem
Let a
4.3 Master theorem (Cont.)
Example:
T (n) be dened on the nonnegative integers by the recurrence
! 1, b > 1 be constants, let f (n) be an asymptotically positive function, and let =
T (n) = aT (n=b) + f (n),
where we interpret n b to mean either n b or n b . Then, T (n) can be bounded asymptotically as follows:
= d=e
Case 1: T (n) = 16T (n=4) + 5. 3n. For this recurrence a = 16, b = 4, f (n) = 5. 3n, we have nlogb a = nlog4 16 = n2 = (n2), f (n) = 5. 3n = O(n2), where = 1. Thus, T (n) = (n2). Case 2: T (n) = T (9n=11) + c. For this recurrence a = 1, b = 11=9, f (n) = c, we have nlogb a = nlog11=9 1 = n0 = (1), f (n) = c = (1). Thus, T (n) = (log n). Case 3: T (n) = 3T (n=4) + n log n. For this recurrence a = 3, b = 4, f (n) = n log n, we have nlogb a = nlog4 3 = O(n0.793). Since f (n) = n log n = (nlog4 3+) where % 0. 2, Case 3 applies if we can show, for sufciently large n, a f (n=b) = 3 (n=4) log(n=4) = (3n=4) log n n log n for = 3=4 < 1. Thus, T (n) = ( f (n)) = (n log n).
If f (n) = O(nlogb a) for some constant > 0, then T (n) = (nlogb a). If f (n) = (nlogb a), then T (n) = (nlogb a lg n). If f (n) = (nlogb a+) for some constant > 0 and if a f (n=b) f (n) for some constant < 1 and sufciently large n, then T (n) = ( f (n)).
Note: logb a = ln a ln b. COMP3600/6466: Lecture 5 2011 15
COMP3600/6466: Lecture 5
2011
16
4.3 Master theorem (Cont.)
There are limitations when applying the Master theorem. For example: T (n) = T (n 2) + n log n. It appears to have the proper from: a = 2, b = 2, f (n) = n log n, and nlogb a = n. You might mistakenly think case 3 should apply, since f (n) is asymptotically larger than
nlogb a = n. The problem is that it is not polynomially larger. f (n)=nlogb a = log n is asymptotically less than n for any positive constant . Thus, it falls into the gap
between case 2 and case 3.
COMP3600/6466: Lecture 5
2011
17
