Chapter 4 - Cookbook Methods for Solving Recurrences

Resources

1. Wikipedia - http://en.wikipedia.org/wiki/Master_theorem
2. Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html
3. Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf
4. Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf

Overview

If we do not know the exact closed-end equation for T(n):

1. perhaps by backward or forward substitution find exact equation or experience, make good guess, prove holds by substituting into induction,
   

2. if no guess, use recursion tree to approximate T(n) bounds and use as the guess, prove by substituting into induction,
   

3. if divide-and-conquer recurrence, can often use master method directly.

 

Master Method for Divide and Conquer

T(n) = a * T(n/b) + f(n)

• a  the number of subproblems
  

• b  determines the size of subproblems
  

• f(n) the cost of each recurrence

Example

MergeSort: T(n) = 2T(n/2) + O(n)

a = 2

b = 2

f(n) = O(n)

Example

The run time cost of f(n) is defined by the recurrence, T(n):

f(n)     if n == 1 return  // Cost 6     else                          f(n/2)                        f(n/2)        f(n/2)        f(n/2)          return              // Cost 5

T(1) = 6                     for n=1 T(n) = 4T(n/2) + 5     for all n>1

Master Theorem - Divide and Conquer

T(n) = a * T(n/b) + f(n)                           where n/b replaces either ⌊n/b⌋ or ⌈n/b⌉ a ≥ 1 the number of subproblems b > 1 determines the problem size f(n) = D(n)+C(n) is a function describing the cost of dividing and combining T(n) can be asymptotically bounded for 3 cases as follows: f(n) < nlogba                Intuitively: cost is dominated by leaves, T(n/b). If f(n) = O(nlogba - ε ) for some constant ε > 0 then T(n) ∈ Θ ( nlogba )   f(n) = nlogba If f(n) = Θ(nlogba ) then T(n) ∈ Θ(nlogba * lg n)   f(n) > nlogba           Intuitively: cost is dominated by root, f(n). If f(n) = Ω(nlogba +ε ) for some constant ε > 0 and af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n then T(n) ∈ Θ(f(n)) i.e. f(n) is polynomially greater than nlogba

Question

Note that when applicable, Master Method determines a recurrence to be Θ.

Are all recurrences Θ?

 

Example - Case 1

T(n) = a * T(n/b) + f(n)

b - rate problem size divided

a - rate number of problems grows

f(n) - cost of each recurrence or to solve a problem of size n

n^log_b^a = a^log_bⁿ - number of size 1 problems

f(n) < nlogba                Intuitively: cost is dominated by leaves, T(n/b). If f(n) = O(nlogba - ε ) for some constant ε > 0 then T(n) ∈ Θ ( nlogba )

T(n) = 9T(n/3) + n                                                     f(n) < n^log_b^a

a = 9        b = 3         f(n) = n                             

n^log_b^a = n^log₃⁹ = n^log₃3² = n²                             n < n^log₃⁹ = n²

If f(n) = O(n^log₃^{9 - ε} ) for some constant ε > 0, then T(n) Θ(n^log_b^a)

f(n) = n = O(n^log₃^{9 - ε} ) = O(n^{2 - ε}) = O(n^{2 - 1}) = O(n) where ε = 1 can apply Case 1 and conclude:

T(n) = Θ(n^log₃⁹) = Θ(n²)

 

Example - Case 1

T(n) = a * T(n/b) + f(n)

f(n) < nlogba                Intuitively: cost is dominated by leaves, T(n/b). If f(n) = O(nlogba - ε ) for some constant ε > 0 then T(n) ∈ Θ ( nlogba )

T(n) = 8T(n/2) + Θ(n²)                                                   

a = 8       b = 2       f(n) = Θ(n²) ⇒ f(n) = O(n²)

n^log₂⁸ = n³                                                                     n² < n^log₂⁸ = n³

If f(n) = O(n^log₂^{8 - ε} ) for some constant ε > 0, then T(n) Θ(n^log_b^a)

f(n) = O(n^log₂^8-ε ) = O(n^log₂^8-1 )  = O(n^3-1 ) = O(n²) where ε = 1 can apply Case 1 and conclude:

T(n) = Θ (n^log₂⁸) = Θ(n^{lg 8})  = Θ(n³)

 

Question 4.14 - Use Case 1 to determine:

T(n) = 16T(n/4) + n ⇒ T(n) = Θ(n²)

 

Example - Case 2

T(n) = a * T(n/b) + f(n)

b - rate problem size divided

a - rate number of problems grows

f(n) - cost of each recurrence or to solve a problem of size n

n^log_b^a = a^log_bⁿ - number of size 1 problems

f(n) = nlogba If f(n) = Θ( nlogba ) then T(n) ∈ Θ( nlogba * lg n )

T(n) = T(2n/3) + 1 = T(n/(3/2)) + 1                1 = n⁰ = n^log_3/2¹ = n⁰

a = 1       b = 3/2         f(n) = 1

n^log_3/2¹ = n⁰ = 1                                   Recall: log_b 1 = 0

If f(n) = Θ( n^log_b^a ) then T(n) ∈ Θ( n^log_b^a * lg n )

f(n) = 1 = Θ(n^log_3/2¹) = Θ(n⁰) = Θ(1)

T(n) = Θ (n^log_3/2¹ lg n) = Θ(lg n)

 

Question 4.15 - Use Case 2 to determine:

T(n) = 4T(n/2) + n² ⇒ T(n) = Θ(n² lg n)

 

Example - Case 2 (More general than text Theorem 4.1)

T(n) = a * T(n/b) + f(n)

f(n) = nlogba If f(n) = Θ( nlogba ) then T(n) ∈ Θ( nlogba * lg n )

T(n) = 27T(n/3) + Θ(n³ lg n)

a = 27         b = 3       f(n) = Θ(n³ lg n)

n^log₃²⁷ = n³

If f(n) = Θ(nlogba (lg n)k ) then T(n) ∈ Θ(nlogba (lg n)k+1)

f(n) = Θ(n^log₃²⁷ (lg n)¹) = Θ(n³ (lg n)¹)

T(n) = Θ(n³ (lg n)²)

f(n) = Θ(n^log_b^a (lg n)^k ), where k ≥ 0.

    This formulation of Case 2 is more general than in Theorem 4.1, and it is given in Exercise 4.4-2.

    f(n) is within a polylog factor of n^log_b^a, but not smaller.

f(n) = Θ(n³ (lg n)¹) within factor (lg n)¹ of n³

Solution: T(n) = Θ(n^log_b^a (lg n)^k+1 )

T(n) = Θ(n^log₃²⁷ (lg n)¹⁺¹ ) = Θ(n^log₃²⁷ (lg n)² ) = Θ(n³ (lg n)² )
Intuitively: cost is n^log_b^a (lg n)^k at each level, and there are Θ(lg n) levels.

Simple case: k = 0 → f (n) = Θ(n^log_b^a) → T (n) = Θ(n^log_b^a lg n ).

Example - Case 3

T(n) = a * T(n/b) + f(n)

b - rate problem size divided

a - rate number of problems grows

f(n) - cost of each recurrence or to solve a problem of size n

n^log_b^a = a^log_bⁿ - number of size 1 problems

f(n) > nlogba                               Intuitively: cost is dominated by root, f(n). If f(n) = Ω( nlogba +ε ) for some constant ε > 0 and af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n then T(n) ∈ Θ(f(n))

T(n) = 3T(n/4) + n lg n                                            n lg n > n^log₄³ = n^0.793

a = 3       b = 4       f(n) =  n lg n

n^log₄³ ≈ n^0.793

If f(n) = Ω( n^log_b^a+ε ) for some constant ε > 0,

f(n) = n lg n = Ω( n^log₄^3+ε ) = Ω( n^0.793+ε ) = Ω( n¹ ) for ε ≈ 0.2

and

if af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n

f(n) = n lg n

af( n/b )	= 3(n/4) lg (n/4)
	= 3/4 n [ lg(n/4) ]
	= 3/4 n [ lg n - lg 4]
	= 3/4 n [ lg n - lg 22]
	= 3/4 n [ lg n - 2]
	= 3/4 n lg n - 3n/2
	≤ 3/4 n lg n
for c = 3/4	= c n lg n
	= c f(n)

then T(n) ∈ Θ( f(n) ) = Θ( n lg n )

 

Question 4.16 - Use Case 3 to determine:

T(n) = 3T(n/2) + n² ⇒ T(n) = Θ(n²)

Hint: Not necessary to find an exact e, just that  f(n) = Ω( n^log_b^a+ε ) =  Ω( n² )  for some constant ε > 0, see graph.

If cg(n) ≤ f(n), c > 0 and ∀ n ≥ n0, then f(n) ∈ Ω(g(n))

T(n) = a * T(n/b) + f(n) f(n) > nlogba                              Intuitively: cost is dominated by root, f(n). If f(n) = Ω( nlogba +ε ) for some constant ε > 0 and af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n then T(n) ∈ Θ(f(n))

Example - Master method does not apply

T(n) = 2T( n/2 ) + n lg n

a=2       b=2      f(n) = n lg n

n^log₂² = n

 

Case 1: Does not apply because

f(n) = n lg n ≥ O(n^log₂²) = O(n)

so cannot subtract ε.

f(n) < nlogba                If f(n) = O( nlogba - ε ) for some constant ε > 0 then T(n) ∈ Θ( nlogba )

O  f(n) / g(n) = c for some 0 ≤ c < ∞

but n lg n/n = ∞

 

T(n) = 2T( n/2 ) + n lg n

a=2       b=2      f(n) = n lg n

n^log₂² = n

Case 2: Does not apply because

f(n) = n lg n ≠ Θ( n^log₂² ) = Θ(n)

and f(n) = n lg n not O(n)

f(n) = nlogba If f(n) = Θ(nlogba ) then T(n) ∈ Θ(nlogba * lg n)

Θ  f(n) / g(n) = c for some 0 < c < ∞

but n lg n/n = ∞

 

T(n) = 2T( n/2 ) + n lg n

a=2       b=2      f(n) = n lg n

n^log₂² = n

Case 3: If f(n) = Ω(n^log_b^a+ε ) for some constant ε > 0,

f(n) > nlogba           If f(n) = Ω(nlogba + ε ) for some constant ε > 0 and af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n then T(n) ∈ Θ(f(n))

Fails because while:

f(n) = n lg n = Ω( n^log₂² ) = Ω(n¹) = Ω(n)

f(n) = n lg n ≠ Ω( n^1+ε ) for any choice of ε > 0 so cannot add ε

To see this, recall:

ω  f(n) / g(n) = c for some 0 < c ≤ ∞

f(n)/n^log₂² = n lg n / n¹ = lg n

so n lg n / n¹ = lg n = ∞

but f(n) must be polynomially larger than n^log_b^a for n lg n / n^1+ε to hold.

n² is polynomially larger than n¹.

lg n / n^ε → 0 for any constant ε > 0

n lg n/n^1+ε =

n lg n/n¹n^ε =

lg n / n^ε → 0                 for any constant ε > 0

The graph shows that lg n grows more slowly than n^0.25

 

Method for Chip & Conquer

The problem of size n is chipped down into one subproblem of size n-c.

T(n) = T(n - c) + f(n) If c > 0 (the chipping factor) f(n) - nonrecursive cost (to create subproblem and/or combine with solutions of other subproblems) then T(n) can be asymptotically bounded as follows: If f(n) is a polynomial nα, then T(n) ∈ Θ(nα+1) If f(n) is lg n, then T(n) ∈ Θ(n lg n)

Example - Factorial

int factorial( n ) {    if ( n == 1) return 1;    return n * factorial( n-1 ); }

Recurrence equation:

| e                     if n = 1 T(n) = |            | T(n - 1) + d     if n > 1

f(n) = d so is a 0-degree polynomial, n⁰

T(n) ∈ Θ(n⁰⁺¹) = Θ(n)

 

Question 4.17 - Use Chip-and-Conquer to determine:

T(n) = T(n-4) + n² ⇒ T(n) = Θ(n³)

Method for Chip & Be Conquered

The problem of size n is chipped down into one subproblem of size n-c.

T(n) = b * T(n - c) + f(n) If b > 1 (the branching factor) c > 0 (the chipping factor) f(n) - nonrecursive cost (to create subproblem and/or combine with solutions of other subproblems) then T(n) in most cases can be bounded as T(n) Θ(bn/c).

Grows exponentially in n so, in general cannot solve problems of significant size.

Example

| e                       if n = 1 T(n) = |            | 5T(n - 1) + d     if n > 1

b = 5

c = 1

f(n) = d

T(n) ∈ Θ(b^n/c) = Θ(5^n/1) = Θ( 5ⁿ )

 

Question 4.18 - Use Chip-and-be-Conquered to determine bounds for:

T(n) = 7T(n-4) + n²