5.15

Let a = 64 and b = 4 in the Master Theorem.
Then n^log_ba = n^log₄64 = n³. We compare each f(n) with n³. (a) T(n) = 64 T(n/4) + n⁴
f(n) = n⁴ = Ω(n³·n¹) = Ω(n³⁺¹). Since 64·(n/4)⁴ = n⁴/4 ≤ c·n⁴ with c = ¼ < 1, the regularity condition holds. Case 3 ⇒ T(n) = Θ(n⁴). (b) T(n) = 64 T(n/4) + n³
f(n) = n³ = Θ(n^log₄64). Case 2 ⇒ T(n) = Θ(n³ log n). (c) T(n) = 64 T(n/4) + 128
f(n) = Θ(1) = O(n^{3 – ε}) for ε = 3. Case 1 ⇒ T(n) = Θ(n³). Hence: (a) Θ(n⁴), (b) Θ(n³ log n), (c) Θ(n³).

Back to Chapter 5