Chapter 4 Answers

Recurrence Relation Tutorial

Question 4.1 - What is T(23)? 34.

Question 4.2 - Is T(1) necessary? Yes when ⌈n/2⌉ = 1.

Question 4.3.1

Inductive proofs on the recurrence: T(n) = T(n-1) + 1

Typically assume the case for parameter n that generates a sequence term for recurrence T(n) and prove T(n+1)=T((n+1)-1)+1.

For above recurrence: T(n) = T(⌊n/4⌋) + n

• What is the next sequence term T(n+1)?  T(n+1) = T(⌊(n+1)/4⌋) + (n+1)

Question 4.3.2    For above recurrence:

• What is the next value of n? 2*n
   

• What is the next term after T(2^k)? T(2^k+1)

 

METHODS FOR SOLVING RECURRENCE RELATIONS

Question 4.4

T(n) = T(n-1)+1 for n > 0               

T(0)=1                                        

Generate

T(1)=2                                       

T(2)=3                                       

T(3)=4                                       

Closed form

Observe pattern T(n) = n + 1

Question 4.5 - Use substitution to prove T(n) = closed form

Question 4.6 - Use induction to prove T(n) = closed form

Substitution T(n) = T(n-1)+1 Basis T(1)=1+1=2 T(n) = n + 1        = (n-1+1)+1        = T(n-1)+1

Induction Basis step T(1)=1+1=2 Inductive Hypothesis T(n) = T(n-1)+1 = n+1 Inductive step Show: T(n+1) = (n+1) + 1 = n+2 T(n+1) = T(n+1-1)+1            Recurrence T(n) = T(n-1)+1            = T(n) + 1            = (n+1)+1                  IH: T(n) = n+1            = n + 2                       ∴

SUBSTITUTION METHOD

Question 4.7 - Use backward substitution to find the closed-end equation for:

T(1) = 1              

T(n) = T(n-1) + 5  for n>1

Solution

By backward substitution the recurrence yields:

T(n)	= T(n-1) + 5	= T(n-2)+5 + 5	sub. T(n-1) = T(n-2)+5
	= T(n-2)+2*5	= T(n-3)+5 + 2*5	sub. T(n-2) = T(n-3)+5
	= T(n-3)+3*5	= T(n-3)+5 + 3*5	sub. T(n-3) = T(n-4)+5
	= T(n-4)+4*5

Substituting i times yields (we're in luck, no summation!):

T(n)= T(n-i) + i*5

Closed-end

Base:  T(1) = T(n-i)

n-i = 1 or i=n-1

T(1) = T(1-i) = T(1-(n-1)) = T(1-(1-1)) = T(1)

Closed-end solution by substitution:

T(n)	= T(n-i) + i*5
	= T(n-(n-1)) + (n-1)*5
	= T(1) + (n-1)*5
	= 1 + (n-1)*5
	= 5n-4

Proof: T(n) = 5n-4

T(1) = 1

T(n) = T(n-i) + 5 for n>1

Base:

T(1) = 5n-4 = 1*5-4 = 1

Assumption:

T(n) = 5n-4

Show:

T(n+1) = 5(n+1) - 4

T(n+1)	= T(n+1-1) + 5
	= T(n) + 5
	= 5n-4+5
	= 5(n+1) - 4

 

Question 4.8 - Is T(n) ≤ 2n lg n = O(n lg n) an exact solution for T(n)? No. But holds for definition of O(n lg n).

Question 4.9 - A reasonable recurrence for the following factorial algorithm is:

T(n) = T(n-1) + 1

FACTORIAL(n)     if n = 1 then return 1     else return FACTORIAL(n-1) * n

Use the substitution method to show that T(n) ∈ O(n)

T(1) = T(n) =

1                            T(n-1) + 1

1. Guess:

   T(n) = O(n)

   By definition of Big-O, must find c > 0 and n ≥ n₀

   0 ≤ T(n) ≤ cn

2. IH

   T(k-1) ≤ c(k-1)

   Show

    T(k) ≤ T(k-1) + 1 ≤ ck

3. Substitution

   T(k) = T(k-1) +1   Recurrence   ≤ c(k-1) + 1   IH substitution   = ck - c + 1     ≤ ck    Find constant c so the last two lines hold.    ck - c + 1 ≤  ck -c + 1 ≤ 0 c ≥ 1 c ≥ 1 satisfies the substitution

    

4. Base or boundary conditions: Now find c and n₀ to satisfy O definition

   Verify: T_R(n) ≤ T_C(n)

   T_R(n) = T(n)                             recurrence

   T_C(n) = cn                                closed-end bounds solution for O(n)

   where TR(n) =

   TR(n-1) + 1

   Try n0 = 2

   TR(n) ≤ TC(n) TR(2) ≤ TC(2) T(2-1) + 1 ≤ c(2) 1 + 1 ≤ 2c c ≥ 1  Succeeds for n0 = 2

   Note:

   Choose c ≥ 1 for boundary condition since it also satisfies above substitution, c ≥ 0.

   The base case of the recurrence, T(1) = 1, is not used for the induction.

   The base case was established by finding c ≥ 1 and n₀ = 2.

5. Closed-end bounds form:

   T(n) ≤ n for n ≥ 2, c = 1

6. Check, verify closed-end bounds form by O definition:

0 ≤ T(n) ≤ cn

T(n) ≤ n = O(n)

c ≥ 1 and n ≥ n₀ = 2

0	≤ T(n)	≤ cn
0	≤ n	≤ cn
0	≤ n/n	≤ c
0	≤ 1	≤ c
	Holds for c ≥ 1

Question 4.9.1

Show that substitution fails to demonstrate that T(n) O(n²):

| 2                        if n = 1 T(n) = |            | 9T(n/3) + n        if n > 1

O(n²): 0 ≤ T(n) ≤ cn²

IH: Assume holds for n/3, that is:

T(n/3) ≤ c(n/3)² is true

Show: T(n) ≤ cn²

T(n) = 9T(n/3) + n            ≤ 9(c(n/3)2)+n   = cn2+n   ≤ cn2

Recurrence IH substitution fails for c > 0

Question 4.9.2

Subtract a lower-order term and use substitution to show that T(n) O(n²):

| 2                        if n = 1 T(n) = |            | 9T(n/3) + n        if n > 1

O(n²): 0 ≤ T(n) ≤ cn² - bn

IH: Assume holds for n/3, that is:

T(n/3) ≤ c(n/3)² - bn/3 is true

Show: T(n) ≤ cn² - bn

T(n) = 9T(n/3) + n                      ≤  9( c(n/3)2 - bn/3 ) + n   = cn2 - 3bn + n   ≤ cn2 - bn   which holds for c > 0 choosing b ≥ 1/2

Solve for b IH substitution

Base case: Find n₀ 

Verify: T(n) ≤ cn² - bn

where T(n) =	2                      when n = 1
	9T(n/3) + n      when n > 1

and      cn² - bn                                            solution for O(n²)

Try n0 = 3

9T(n/3) + n ≤ cn2 - bn   9T(3/3) + n ≤ c32 - b3    n0=3 21 ≤ 9c - 3b   9c ≥ 3b + 21   b ≥ 1/2 9c ≥ 22 1/2   b = 1/2 9c ≥ 45/2   c ≥ 5/2    holds for n0 = 3 and c ≥ 2 1/2

Question 4.10

| d                        if n = 1 T(n) = |            | 4T(⌊n/2⌋) + dn     if n > 1

Show that substitution fails to demonstrate that T(n) O(n²):

O(n²): 0 ≤ T(n) ≤ cn²

Basis:

Choose n₀=1

Prove basis holds for n₀

T(1) = d ≤ c1² = c        holds for c ≥ d

IH: Assume holds for n/2, that is:

T(⌊n/2) ≤ c(⌊n/2⌋)² is true

Show: T(n) ≤ cn²

• cn² in the verification below does not work for d > 0.

T(n) = 4T(⌊n/2⌋) + dn               Recurrence   = 4[c(⌊n/2⌋)2] + dn            IH substitution   ≤ 4[c(n/2)2] + dn   = cn2+dn   ≤ cn2

cn2+dn ≤ cn2   (⌊n/2⌋)2 ≤ (n/2)2   fails for d > 0

Question 4.11

    Substitution subtlety

• cn²-bn does work for d > 0, n₀=1.

  Basis:

  Choose n₀=1

  Prove basis holds for n₀

  T(n₀) = d ≤ cn₀²-b*n₀

  T(1) = d ≤ c1²-b*1 = c-b        holds for c ≥ d+b

  IH: Assume holds for n/2, that is:

  T(n/2) ≤ c(n/2)² - bn/2

  Show: T(n) ≤ cn² - bn

T(n) = 4T(⌊n/2⌋) + dn                    Recurrence   = 4[c(n/2)2 - bn/2] + dn              IH substitution   = cn2 - 2bn + dn   ≤ cn2 - bn   which holds for c > 0 choosing b ≥ d

Solve for b cn2 - 2bn + dn ≤ cn2 - bn      -2bn + dn ≤ -bn          -2b + d ≤ -b                 d ≤ b                 b ≥ d

Question 4.10.1

Show that substitution fails to demonstrate that T(n) O(n^{lg 3}):

where T(n) =	1                      when n = 1
	3T(n/2) + n      when n > 1

1. Guess:

   T(n) = O(n^{lg 3})

   By definition of Big-O, must find c > 0 and n ≥ n₀ > 0

   0 ≤ T(n) ≤ cn^{lg 3}

2. IH:     T(n/2) ≤ c(n/2)^{lg 3}
    

3. Induction Step:

   T(n)	=	3T(n/2) + n	Recurrence
   	≤	3c(n/2)lg 3 + n	substitution of IH
   	=	3c(nlg 3/2lg 3) + n
   	=	3c(nlg 3/3) + n	2lg 3 = 3lg 2 = 3
   	=	cnlg 3 + n
   	≤	cnlg 3	fails

   Induction fails, because must show exactly that:

   T(n) ≤ cn^{lg 3}

Question 4.11.1

Subtract a lower-order term and use substitution to show that T(n) O(n^{lg 3}):

where T(n) =	1                      when n = 1
	3T(n/2) + n      when n > 1

1. Guess:

   T(n) = O(n^{lg 3})

   By definition of Big-O, must find c > 0 and n ≥ n₀ > 0

   0 ≤ T(n) ≤ cn^{lg 3} - bn

2. IH:     T(n/2) ≤ c(n/2)^{lg 3} - bn/2
    

3. Induction Step:

   T(n)	=	3T(n/2) + n	Recurrence
   	≤	3[c(n/2)lg 3 - bn/2] + n	substitution of IH
   	=	3[c(nlg 3/2lg 3) - bn/2] + n
   	=	3[cnlg 3/3) - bn/2] + n	2lg 3 = 3lg 2 = 3
   	=	cnlg 3 - 3bn/2 + n
   	≤	cnlg 3 - bn

    

4. Find b

cnlg 3 - 3bn/2 + n	≤	cnlg 3 - bn
n	≤	3bn/2-bn
	=	3bn/2-2bn/2
	=	(3bn-2bn)/2
	=	bn/2
2n	≤	bn
2	≤	b
b	≥	2

Base case: Find n₀ 

where T(n) =	1                      when n = 1
	3T(n/2) + n      when n > 1

Verify: 0 ≤ T(n) ≤ cn^{lg 3} - bn

Try n0 = 2 an even number

3T(n/2) + n ≤ cnlg 3 - bn   nlg 3=3lg n 3T(2/2) + n ≤ c3lg 2 - b2      n0=2 3T(1) + 2 ≤ 3c-2b   3lg 2=31 3*1 + 2 ≤ 3c-2b     5 ≤ 3c-2b     2b+5 ≤ 3c     3c ≥ 2b+5       b ≥ 2 3c ≥ 9     c ≥ 3      holds for n0 = 2 and c ≥ 3

5.  Choose: c ≥ 3 and n₀ = 2

Since T(n) ≤ cn^{lg 3} - bn, ∀n ≥ n₀ when b ≥ 2, c ≥ 3 and n₀ = 2

 T(n) ∈ O(n^{lg 3})

Question 4.12 - Draw the recursion tree.

| c                        if n = 1 T(n) = |            | 4T(⌊n/2⌋) + cn     if n > 1

Question 4.13 - For:

| c                        if n = 1 T(n) = |            | 4T(⌊n/2⌋) + cn     if n > 1

2. From the tree determine:
   1. # of levels in the tree of height lg n:

      0..lg n

   2. cost per level at level i:

      2ⁱcn

   3. # of nodes in the last level, problem size n=1:

      4^{lg n} = n^{lg 4} = n²

   4. cost of the last level:

      T(1) * n² = c * n² = cn² = Θ(n²)

3. Write down the summation using ∑ notation. Summation of cost for lg n levels in the recursion tree + bottom level.

   T(n) =

4. Find closed form solution for the summation created in 3) using Appendix A.

   T(n) =
   =	cn(2lg n-1)/(2-1)+cn2	App. A5 p. 1147
   =	cn(2lg n-1)/(2-1)+cn2
   =	cn(2lg n-1)+cn2
   =	cn(nlg 2-1)+cn2
   =	cn(n-1)+cn2
   =	cn2-cn+cn2
   =	2cn2-cn

   Total: cost of each level * the number of levels + cost of bottom level.

   

5. Use closed form solution as “guess” in terms of Big-O, or Θ, or Ω (depending on which type of asymptotic bound is being sought).

   T(n)	= 2cn2-cn
   	= O(n2)

6. Then use Substitution Method or Master Method to prove that the bound is correct.

   See Question 4.10 and 4.11 for Substitution Method.

    

Question 4.14 - Use Case 1 to determine:

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

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

a = 16       b = 4       f(n) = n = O(n)

n^log₄¹⁶ = n^log₄4²= n²

If f(n) = O(n^log₄^{16 - ε} ) for some constant ε > 0, then T(n) Θ(n^log₄¹⁶)

f(n) = O(n^log₄^16-ε ) = O( n^log₄^16-1 ) = O( n^2-1 ) = O(n) where ε = 1 can apply Case 1 and conclude:

T(n) = Θ (n^log₄¹⁶) = Θ(n²)

Question 4.15 - Use Case 2 to determine:

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

a = 4       b = 2         f(n) = 1

n^log₂⁴ = n²

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

f(n) = n² = Θ(n^log₂⁴) = Θ(n²)

T(n) = Θ (n^log₂⁴ lg n) = Θ(n² lg n)

Question 4.16 - Use Case 3 to determine:

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

a = 3       b = 2       f(n) = n²

n^log₂³ ≈ n^1.58

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

f(n) = n² = Ω( n^log₂^3+ε ) = Ω( n^1.58+ε ) = Ω( n² ) for ε ≈ 0.42

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

a = 3    b = 2    f(n) = n²

af( n/b )	= 3(n/2)2
	= 3n2/4
	≤ 3/4 n2
for c = 3/4	= c n2
	= c f(n)

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

   T(n) = Θ(n²)

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

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

 f(n) is a polynomial n², then T(n) ∈ Θ(n²⁺¹) =  Θ(n³)

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

T(n) = 7T(n-4) + n² ⇒ T(n) = Θ(7^n/4)