16.
070
Introduction to Computers & Programming
Algorithms: Recurrence
Prof. Kristina Lundqvist
Dept. of Aero/Astro, MIT
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Recurrence
§ If 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.
§ Many natural functions are easily expressed as recurrences
§ an = an-1 + 1; a1 = 1 => an = n (linear)
§ an = an-1+ 2n - 1; a1 = 1 => an = n2 (polynomial)
§ an = 2an-1; a1 = 1 => an = 2n (exponential)
§ an = n an-1; a1 = 1 => an = n! (others…)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Recurrence
§ Recursion is Mathematical Induction
§ In both, we have general and boundary conditions,
with the general condition breaking the problem
into smaller and smaller pieces.
§ The initial or boundary condition terminate the
recursion.
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Recurrence Equations
§ A recurrence equation defines a function, say T(n).
The function is defined recursively, that is, the function T(.)
appear in its definition. (recall recursive function call).
The recurrence equation should have a base case.
For example:
T(n) = T(n-1)+T(n-2), if n>1
1, if n=1 or n=0
base case
for convenience, we sometime write the recurrence equation as:
T(n) = T(n-1)+T(n-2)
T(0) = T(1) = 1
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Recurrences
§ The expression:
c n =1
T ( n) =
2T n + cn n > 1
2
is a recurrence.
§ Recurrence: an equation that describes a function in terms of its
value on smaller functions
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Recurrence Examples
0 n=0 0 n=0
s(n ) = s(n ) =
c + s(n − 1) n > 0 n + s(n − 1) n > 0
c n =1 c n =1
T ( n) = T ( n) =
2T n + c n > 1 n
2 aT + cn n > 1
b
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Calculating Running Time
Through Recurrence Equation (1/2)
Algorithm A min1(a[1],a[2],…,a[n]):
1. If n == 1, return a[1]
2. m := min1(a[1],a[2],…,a[n-1] )
3. If m > a[n], return a[n], else return m
§ Now, let’s count the number of comparisons
§ Let T(n) be the total number of comparisons (in step 1 and 3).
T(n) = 1 + T(n -1) + 1; T(n) = n + 1, if n >1
T(1) = 1;
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Calculating Running Time
Through Recurrence Equation (2/2)
Algorithm B min2(a[1],a[2],…,a[n]):
1. If n == 1 return the minimum of a[1];
2. Let m1 := min2( a[1], a[2], …, a[ n / 2 ] );
Let m2 := min2( a[n/2+1],a[n/2+2],…., a[n] );
3. If m1 > m2 return m1 else return m2
§ For n>2, T(n) = T(n/2) + T(n/2) + 1, T(n) = ?
T(1)=1
§ To be precise, T(n) = T( n/2) + T( n/2 ) + 1,
but for convenient, we ignore the “ceiling” and “floor”
and assume n is a power of 2.
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
More Recurrence equations
T(n) = 2 * T(n/2) + 1,
T(1) = 1. Base case;
initial condition.
T(n) = T(n-1) + n,
Selection Sort
T(1) = 1.
T(n) = 2* T(n/2) + n, Merge Sort
T(1) = 1.
T(n) = T(n/2) + 1, Binary search
T(1) = 0.
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Solve a recurrence relation
We can use mathematical induction to prove that a general
function solves for a recursive one. Guess a solution and prove
it by induction.
Tn = 2Tn-1 + 1 ; T0 = 0
n = 0 1 2 3 4 5 6 7 8
Tn = 0 1 3 7 15 31 63 …
Guess what the solution is?
Tn = 2 n - 1
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Solve a recurrence relation
Prove: Tn = 2n - 1 by induction:
1. Show the base case is true: T0 = 20 - 1 = 0
2. Now assume true for Tn-1
3. Substitute in Tn-1 in recurrence for Tn
Tn = 2Tn-1 + 1
= 2 ( 2n-1 - 1 ) + 1
= 2n -1
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Solving Recurrences
There are 3 general methods for solving recurrences
1. Substitution: “Guess & Verify”: guess a solution
and verify it is correct with an inductive proof
2. Iteration: “Convert to Summation”: convert the
recurrence into a summation (by expanding some
terms) and then bound the summation
3. Apply “Master Theorem”: if the recurrence has the
form
T(n) =aT (n/b) +f(n)
then there is a formula that can (often) be applied.
Recurrence formulas are notoriously difficult to derive,
but easy to prove valid once you have them
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Simplications
§ There are two simplications we apply that won't
affect asymptotic analysis
§ ignore floors and ceilings
§ assume base cases are constant, i.e., T(n) = Θ(1) for n
small enough
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Solving Recurrences: Substitution
§ This method involves guessing form of solution
§ use mathematical induction to find the constants
and verify solution
§ use to find an upper or a lower bound (do both to
obtain a tight bound)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
The Substitution method
Solve: T(n) = 2T(n/2) + n
§ Guess: T(n) = O(n lg n), that is: T(n) ≤ cn lg n
§ Prove:
§ Base case: assume constant size inputs take const time
§ T(n) ≤ cn lg n for a choice of constant c > 0
§ Assume that the bound holds for n/2, that is,
that T(n/2) ≤ c n/2 lg(n/2)
Substituting into the recurrence yields:
T(n) ≤ 2(c n/2 lg (n/2)) + n
≤ cn lg(n/2) + n
= cn lg n – cn lg 2 + n
= cn lg n - cn + n Where last step
holds as long as
≤ cn lg n c≥1
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Example
Example: T(n) = 4T(n/2) + n (upper bound)
guess T(n) = O(n3) and try to show T(n) < cn3 for some
c > 0 (we'll have to find c)
basis ?
assume T(k) < ck3 for k < n, and prove T(n) < cn3
T(n) = 4T(n/2) + n
< 4(c(n/2)3 + n
= c/2n3 + n
= cn3 -(c/2n3 - n)
< cn3
where the last step holds if c > 2 and n > 1
We find values of c and n0 by determining when c/2n3 - n > 0
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Solving Recurrences by Guessing (1/3)
§ Guess the form of the answer, then use induction to find
the constants and show that solution works
§ Examples:
§ T(n) = 2T(n/2) + Θ(n) à T(n) = Θ(n lg n)
§ T(n) = 2T(n/2) + n à ???
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Solving Recurrences by Guessing (2/3)
§ Guess the form of the answer, then use induction to find
the constants and show that solution works
§ Examples:
§ T(n) = 2T(n/2) + Θ(n) à T(n) = Θ(n lg n)
§ T(n) = 2T(n/2) + n à T(n) = Θ(n lg n)
§ T(n) = 2T(n/2 + 17) + n à ???
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Solving Recurrences by Guessing (3/3)
§ Guess the form of the answer, then use induction to find
the constants and show that solution works
§ Examples:
§ T(n) = 2T(n/2) + Θ(n) à T(n) = Θ(n lg n)
§ T(n) = 2T(n/2) + n à T(n) = Θ(n lg n)
§ T(n) = 2T(n/2+ 17) + n à Θ(n lg n)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Recursion-Trees
§ Although the substitution method can provide a
succinct proof that a solution to a recurrence is
correct, it is sometimes difficult to come up with a
good guess.
§ Drawing out a recursion-tree is a good way to
devise a good guess.
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Recursion Trees
T(n) = 2 T(n/2) + n2 , T(1) = 1
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Solving Recurrences: Iteration
§ Expand the recurrence
§ Work some algebra to express as a
summation
§ Evaluate the summation
§ We will show several examples
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
00 = 0= 0
nn
( n ) =
s (n ) = c + s (n − 1) n > 0
s
c + s( n − 1) n > 0
§ s(n) =
c + s(n-1)
c + c + s(n-2)
2c + s(n-2)
2c + c + s(n-3)
3c + s(n-3)
…
kc + s(n-k) = ck + s(n-k)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
00 = 0= 0
nn
( n ) =
s (n ) = c + s (n − 1) n > 0
s
c + s( n − 1) n > 0
§ So far for n >= k we have
§ s(n) = ck + s(n-k)
§ What if k = n?
§ s(n) = cn + s(0) = cn
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
0 n=0
s (n ) =
c + s( n − 1) n > 0
§ So far for n >= k we have
§ s(n) = ck + s(n-k)
§ What if k = n?
§ s(n) = cn + s(0) = cn
§ So
0 n=0
s ( n) =
c + s( n − 1) n > 0
§ Thus in general
§ s(n) = cn
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
= 00 n =n0= 0
s(n ) = n + s ( n − 1) n > 0
s( n )
n + s (n − 1) n > 0
§ s(n)
= n + s(n-1)
= n + n-1 + s(n-2)
= n + n-1 + n-2 + s(n-3)
= n + n-1 + n-2 + n-3 + s(n-4)
= …
= n + n-1 + n-2 + n-3 + … + n-(k-1) + s(n-k)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
= 00 n =n0= 0
s(n ) = n + s ( n − 1) n > 0
s( n )
n + s (n − 1) n > 0
§ s(n)
= n + s(n-1)
= n + n-1 + s(n-2)
= n + n-1 + n-2 + s(n-3)
= n + n-1 + n-2 + n-3 + s(n-4)
= …
= n + n-1 + n-2 + n-3 + … + n-(k-1) + s(n-k)
n
=
∑i
i = n − k +1
+ s (n − k )
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
= 00 n =n0= 0
s(n ) = n + s ( n − 1) n > 0
s( n )
n + s (n − 1) n > 0
§ So far for n >= k we have
n
∑i
i = n − k +1
+ s (n − k )
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
= 00 n =n0= 0
s(n ) = n + s ( n − 1) n > 0
s( n )
n + s (n − 1) n > 0
§ So far for n >= k we have
n
∑i
i = n − k +1
+ s (n − k )
§ What if k = n?
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
= 00 n =n0= 0
s(n ) = n + s ( n − 1) n > 0
s( n )
n + s (n − 1) n > 0
§ So far for n >= k we have
n
∑i
i = n − k +1
+ s (n − k )
§ What if k = n?
n
n +1 n
∑
i =1
i + s ( 0) = ∑ i + 0 = n
i =1 2
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
0 n=0
s( n ) =
n + s (n − 1) n > 0
§ So far for n >= k we have
n
∑i
i = n − k +1
+ s (n − k )
§ What if k = n?
n
n +1 n
∑
i =1
i + s ( 0) = ∑ i + 0 = n
i =1 2
§ Thus in general
n +1
s (n ) = n
2
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
T (n) = 2T n + c n > 1
2
§ T(n) =
2T(n/2) + c
2(2T(n/2/2) + c) + c
22T(n/22) + 2c + c
22(2T(n/22/2) + c) + 3c
23T(n/23) + 4c + 3c
23T(n/23) + 7c
23(2T(n/23/2) + c) + 7c
24T(n/24) + 15c
…
2kT(n/2k) + (2k - 1)c
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
T (n) = 2T n + c n > 1
2
§ So far for n > 2k we have
§ T(n) = 2kT(n/2k) + (2k - 1)c
§ What if k = lg n?
§ T(n) = 2lg n T(n/2lg n) + (2lg n - 1)c
= n T(n/n) + (n - 1)c
= n T(1) + (n-1)c
= nc + (n-1)c = (2n - 1)c
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Solving Recurrences: Iteration
c n =1
n
T ( n) = aT
+ cn n > 1
b
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ T(n) =
aT(n/b) + cn
a(aT(n/b/b) + cn/b) + cn
a2T(n/b2) + cna/b + cn
a2T(n/b2) + cn(a/b + 1)
a2(aT(n/b2/b) + cn/b2) + cn(a/b + 1)
a3T(n/b3) + cn(a2/b2) + cn(a/b + 1)
a3T(n/b3) + cn(a2/b2 + a/b + 1)
…
akT(n/bk) + cn(ak-1/bk-1 + ak-2/bk-2 + … + a2/b2 + a/b + 1)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So we have
§ T(n) = akT(n/bk) + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1)
§ For k = logb n
§ n = bk
§ T(n) = akT(1) + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1)
= akc + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1)
= cak + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1)
= cnak /bk + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1)
= cn(ak/bk + ... + a2/b2 + a/b + 1)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a = b?
§ T(n) = cn(k + 1)
= cn(logb n + 1)
= Θ(n log n)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a < b?
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a < b?
§ Recall that Σ(xk + xk-1 + … + x + 1) = (xk+1 -1)/(x-1)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a < b?
§ Recall that Σ (xk + xk-1 + … + x + 1) = (xk+1 -1)/(x-1)
§ So:
a k a k −1 a
+ k −1 + L + + 1 =
(a b )k +1 − 1 =
1 − (a b)k +1
<
1
k
b b b (a b ) − 1 1 − (a b ) 1− a b
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a < b?
§ Recall that Σ(xk + xk-1 + … + x + 1) = (xk+1 -1)/(x-1)
§ So:
a k a k −1 a
+ k −1 + L + + 1 =
(a b )k +1 − 1 =
1 − (a b)k +1
<
1
k
b b b (a b ) − 1 1 − (a b ) 1− a b
§ T(n) = cn ·Θ(1) = Θ(n)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a > b?
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a > b?
a k a k −1 a
+ k −1 + L + + 1 =
(a b )k +1 − 1 (
= Θ (a b )
k
)
k
b b b (a b ) − 1
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a > b?
a k a k −1 a
+ k −1 + L + + 1 =
(a b )k +1 − 1 (
= Θ (a b )
k
)
k
b b b (a b ) − 1
§ T(n) = cn · Θ(ak / bk)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a > b?
a k a k −1 a
+ k −1 + L + + 1 =
(a b )k +1 − 1 (
= Θ (a b )
k
)
k
b b b (a b ) − 1
§ T(n) = cn · Θ(ak / bk)
= cn · Θ(alog n / blog n) = cn · Θ(alog n / n)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a > b?
a k a k −1 a
+ k −1 + L + + 1 =
(a b )k +1 − 1 (
= Θ (a b )
k
)
k
b b b (a b ) − 1
§ T(n) = cn · Θ(ak / bk)
= cn · Θ(alog n / blog n) = cn · Θ(alog n / n)
recall logarithm fact: alog n = nlog a
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a > b?
a k a k −1 a
+ k −1 + L + + 1 =
(a b )k +1 − 1 (
= Θ (a b )
k
)
k
b b b (a b ) − 1
§ T(n) = cn · Θ(ak / bk)
= cn · Θ(alog n / blog n) = cn · Θ(alog n / n)
recall logarithm fact: alog n = nlog a
= cn · Θ(nlog a / n) = Θ(cn · nlog a / n)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So with k = logb n
§ T(n) = cn(ak/b k + ... + a2/b2 + a/b + 1)
§ What if a > b?
a k a k −1 a
+ k −1 + L + + 1 =
(a b )k +1 − 1 (
= Θ (a b )
k
)
k
b b b (a b ) − 1
§ T(n) = cn · Θ(ak / bk)
= cn · Θ(alog n / blog n) = cn · Θ(alog n / n)
recall logarithm fact: alog n = nlog a
= cn · Θ(nlog a / n) = Θ(cn · nlog a / n)
= Θ(nlog a )
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
c n =1
n
T ( n ) = aT
+ cn n > 1
b
§ So…
Θ(n ) a<b
T (n) = Θ(n log b n ) a=b
(
Θ n log b a
) a>b
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
The Master Method
§ Provides a “cookbook” method for solving
recurrences of the form
§ T(n) = aT(n/b) + f(n), where a ≥ 1 and b > 1 are
constants and f(n) is an asymptotically positive
function.
§ The Master method requires memorization of three
cases, but then the solution of many recurrences can be
determined quite easily, often without pencil and paper.
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
The Master Method
§ Given: a divide and conquer algorithm
§ An algorithm that divides the problem of size n into a
subproblems, each of size n/b
§ Let the cost of each stage (i.e., the work to divide the
problem + combine solved subproblems) be described
by the function f(n)
§ Then, the Master Method gives us a cookbook for
the algorithm’s running time:
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Solving Recurrences: The Master Method
§ Master Theorem: Let a > 1 and b >1 be constants, let f(n)
be a function,and let T(n) be defined on nonnegative
integers as:
T(n) = aT(n/b) + f(n),
Then, T(n) can be bounded asymptotically as follows:
logb a − ε
1. T (n) = Θ(n logb a
) If f (n ) = Θ (n ) for some
constant ε >0
2. T(n) = Θ(n
logb a
log n) If f (n ) = Θ ( n logb a
)
logb a + ε
3. T(n) = Θ(f(n)) If f (n ) = Ω (n ) for some constant ε
>0 and if af(n/b) < cf(n) for some constant c <1 and all
suciently large n.
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
The Master Theorem
§ if T(n) = aT(n/b) + f(n) then
Θ(n )
logb a
f ( n) = O n logb a −ε(
)
ε > 0
(
T (n) = Θ n logb a log n ) f ( n) = Θ n logb a
( )
c <1
Θ( f (n)) (
f (n) = Ω n logb a +ε AND )
af (n / b) < cf (n) for large n
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Solving Recurrences: The Master Method
(cont.)
Intuition: compare f(n) with Θ(nlog a ) b
§ case 1: f(n) is `polynomially smaller than’ Θ(nlog a ) b
§ case 2: f(n) is `asymptotically equal to’ Θ(nlog a ) b
§ case 3: f(n) is `polynomially larger than' Θ(nlog a ) b
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
General Case for Master Theorem
§ In general (Master Theorem, CLR, p.62), T(1) = d,
and for n >1,
T(n) =aT(n/b) +cn
has solution
if a <b, T(n) =O(n);
if a = b, T(n) =O(n log n);
if a >b, T(n) = O(n )
log a b
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Case I
Example: T(n) =9T(n/3 ) +n
§ a = 9,b = 3,f(n) =n, nlogb a = nlog3 9 = n2
§ compare f(n) =n with nlogb a = n2
§ n = O(n2-ε) (f(n) is polynomially smaller than nlogb a )
§ case 1 applies:
T(n) = Θ(nlogb a ) = Θ(n2 )
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Case II
Example: T(n) =T(2n/3 ) +1
§ a = 1, b = 3/2, f(n) = 1,
n logb a
= nlog3 / 2 1
= n0
=1
§ compare f(n) = 1 with n b = 1
log a
§ 1 = Θ(1) (f(n) is asymptotically equal to nlogb a
§ case 2 applies:
T(n) = Θ(nlogb a log n) = Θ(log n)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]
Case III
Example: T(n) =3T(n/4 ) +n log n
§ a = 3, b = 4, f(n) = n log n, nlogb a
= nlog 4 3
= n0.793
§ compare f(n) = n log n with n logb a
= n 0.793
§ n logn = Ω(n0.793− ε ) f(n) is polynomially larger than nlogb a
§ case 3 might apply: need to check `regularity' of f(n)
§ find c < 1 s.t. af(n/b) < cf(n) for large enough n
3n n
§ ie. log ≤ cn log n Which is true for c = ¾
4 4
§ case 3 applies: T(n) = Θ(f(n)) = Θ(n log n)
16.070 — April 30/2003 — Prof. I. K. Lundqvist — kristina@[Link]