SUNY Geneseo Department of Computer Science

Solution to Problem Set 8 (Master Theorem)

Find asymptotic closed forms for each of the following recurrence relations.

Recurrence 1

• T(n) = 1 if n = 0
• T(n) = 8 T(n/2) + n if n > 0

Use the Master Theorem, noting that a = 8, b = 2, and g(n) = n. log₂8 = 3, so g(n) = O( n^{log_ba - ε} ) for ε = 2. Therefore the closed form is T(n) = Θ( n^log_ba ) =  Θ( n^log₂8 ) = Θ( n³ ).

Recurrence 2

• T(n) = 1 if n = 0
• T(n) = 9 T(n/3) + n² if n > 0

Use the Master Theorem, noting that a = 9, b = 3, and g(n) = n². log₃9 = 2, so g(n) = Θ( n^log_ba ). Therefore the closed form is T(n) = Θ( n^log₃9 logn ) =  Θ( n² logn )

Recurrence 3

• T(n) = 17 if n = 1
• T(n) = 3 T(n/2) + n² if n > 1

Use the Master Theorem, noting that a = 3, b = 2, and g(n) = n². log₂3 ≈ 1.58, so g(n) = Ω( n^{log_ba + ε} ) for ε ≈ 0.42. Furthermore, a g(n/b) = 3 (n/2)² = 3/4 n² ≤ c g(n) = c n² for any c ≥ 3/4. Therefore the closed form is T(n) = Θ( g(n) ) =  Θ( n² ).

Recurrence 4

• T(n) = 1 if n = 0
• T(n) = 2 T(n/4) + 2 if n > 0

Use the Master Theorem, with a = 2, b = 4, and g(n) = 2. log₄2 = 0.5, so g(n) = O( n^{log_ba - ε} ) = O( n^0.5 - ε ) for ε = 0.5. Therefore the closed form is T(n) = Θ( n^log_ba ) =  Θ( n^log₄2 ) = Θ( n^0.5 ) = Θ( √n ).