Chapter 4 - Substitution Method

4.3 OVERVIEW - Don't confuse with forward or backward substitution

Substitution as used here, refers to substituting a guess for a closed-end recurrence solution into an induction proof.

To prove asymptotic bounds, Θ or O, of the recurrence T(n) must show holds for some constant c>0.

If we happen to know the exact closed-end equation for T(n), guess a bounds and prove from Θ, Ω or O definition:

Example - With exact closed-end equation for T(n)

O definition: If f(n) ≤ cg(n),  c > 0, ∀ n ≥ n0 then f(n) ∈ O(g(n))

T(n) = n/50

1. Guess n/50 ∈ O(n)
   
2. 0 ≤ n/50 ≤ cn
   
3. 0 ≤ 1/50 ≤ c,                       n₀=1 because n₀=0 has c = 0

Without the exact closed-end equation for T(n), guess a bounds and prove by:

1. if we can find a reasonable bounds guess, perhaps by backward substitution or experience, prove holds by substituting into induction.
   

2. if we can not easily find a good guess, use recursion tree to approximate T(n) bounds and use as the guess; then prove by substituting into induction.
   

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

Example - A reasonable recurrence for the following summation of odd integers algorithm is:

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

-- pre: n is odd SUM(n)     if n = 1 then return 1     else return SUM(n-2) + n

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

T(1) = T(n) =

1                            T(n-2) + 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-2) ≤ c(k-2)

   Show

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

3. Substitution Method

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

    

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

   Verify: T_R(n) ≤ T_C(n)                       Recurrence  ≤  Closed-end

        T_R(n) = T_R(n-2) + 1             Recurrence

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

   Try n0 = 3

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

   Note:

   Choose c ≥ 2/3 for boundary condition since it also satisfies above substitution, c ≥ 1/2.

   The base case of the recurrence, T(1) = 1, is not used for the induction but is used to establish boundary conditions.

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

5. Closed-end bounds form:

   T(n) ≤ cn for n ≥ 3, c = 2/3

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

0 ≤ T(n) ≤ cn

c ≥ 2/3 and n ≥ n₀ = 3

0	≤ T(n)	≤ cn		O definition
0	≤ 2/3 n	≤ cn		Substitute T(n)
0	≤ (2/3 n)/n	≤ c
0	≤ 2/3	≤ c
	Holds for c ≥ 2/3

0 ≤ T(n) ≤ cn = O(n)

Example - Note on page 64 of Edition 2, the text solves this problem but is confused and finds the boundary condition for the wrong recurrence:

T( ⌊n/2⌋ ) + T(⌈n/2⌉ ) + n

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

T(1) = T(n) =

1                            2T( ⌊n/2⌋ ) + n

1. Guess:

   T(n) = O(n lg n)

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

   0 ≤ T(n) ≤ cn lg n

2. IH

   0 ≤ T( ⌊k/2⌋ ) ≤ c ⌊k/2⌋ lg ⌊k/2⌋

   Show:

   T(k) = 2T(⌊k/2⌋) + k ≤ ck lg k           

3. Substitution

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

   Verify: T_R(n) ≤ T_C(n)                      Recurrence  ≤  Closed-end

   T_R(n) = T(n)                             recurrence

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

   where TR(n) =

   2TR( ⌊n/2⌋ ) + n

   Try n0 = 1	Try n0 = 2
   TR(n) ≤ TC(n) TR(1) ≤ TC(1) 2*T(⌊ 1/2 ⌋) + 1 ≤ c(1) lg(1) 1 ≤ c(1) lg(1) 1 ≤ c*0 1 ≤ 0  fails for n0 = 1	TR(n) ≤ TC(n) TR(2) ≤ TC(2) 2*T(⌊ 2/2 ⌋) + 2 ≤ c(2) lg(2) 2*T(1) + 2 ≤ 2c 4 ≤ 2c   succeeds when c ≥ 2 and n0 = 2

   Note:

   • Because T(0) is not defined:    2*T(⌊ 1/2 ⌋) + 1 = 2T(0) + 1 = 1
     
   • We choose the c ≥ 2 for boundary condition since it also satisfies the above, c ≥ 1 satisfies the substitution.
     
   • Also that the base case of the recurrence, T(1) = 1, is not used for the induction.
     
   • The induction base case was established by finding c ≥ 2 and n₀ = 2.
     
   • We just showed induction first then established the base.

     T(k) = 2T(⌊k/2⌋) + k ≤ ck lg k           

    

5. Closed-end bounds form:

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

6. As a check, verify closed-end bounds form by O definition:

   0 ≤ T(n) ≤ cn lg n

   T(n) ≤ 2n lg n = O(n lg n)

   c ≥ 2 and n ≥ n₀ ≥ 2

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

Question 4.8 - Is T(n) ≤ 2n lg n = O(n lg n) an exact solution for T(n)?    Exact meaning: T(n) = 2n 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 Method

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

    

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

   Verify: T_R(n) ≤ T_C(n)                       Recurrence  ≤  Closed-end

        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( ?? ) ≤ TC( ?? ) ???? ≤ ???? c ≥ ????  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 but is used to establish boundary conditions.

   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		O definition
0	≤ n	≤ cn		Substitute T(n)
0	≤ n/n	≤ c
0	≤ 1	≤ c
	Holds for c ≥ 1