5.13

Using the Master/iteration methods:
1. Algorithm [math]A[/math]:   T(n)=5T(n/2)+Θ(n). Here a=5, b=2, f(n)=n, so n^log₂5≈n^2.322 dominates.   T(n)=Θ(n^log₂5) = O(n^2.32).

2. Algorithm [math]B[/math]:   T(n)=2T(n-1)+Θ(1). Unfolding gives T(n)=2·2···2 = 2ⁿ, hence   T(n)=Θ(2ⁿ) = O(2ⁿ).

3. Algorithm [math]C[/math]:   T(n)=9T(n/3)+Θ(n²). Now a=9, b=3, n^log₃9=n², so f(n)=Θ(n²) matches case 2 of the Master Theorem.   T(n)=Θ(n² log n) = O(n² log n).

Asymptotically O(n² log n) < O(n^2.32) << O(2ⁿ), so for large problem sizes the best choice is Algorithm [math]C[/math].

Back to Chapter 5