The solution of the recurrence relation of \(T(n) = 3T(floor(\frac n 4)) + n\)…
2014
The solution of the recurrence relation of \(T(n) = 3T(floor(\frac n 4)) + n\) is
- A.
\(O(n^2)\) - B.
\(O(n \ lg \ n)\) - C.
\(O(n)\) - D.
\(O(l \ g \ n)\)
Attempted by 224 students.
Show answer & explanation
Correct answer: C
Apply the Master theorem to T(n) = 3T(floor(n/4)) + n.
Key parameters:
a = 3
b = 4
f(n) = n
Compute the critical exponent n^{log_b a}:
n^{log_4 3} ≈ n^{0.792}
Compare f(n) with n^{log_b a}:
f(n) = n = Theta(n^1), and 1 > 0.792, so f(n) grows polynomially faster than n^{log_b a}.
Check the regularity condition: 3·f(n/4) = 3·(n/4) = 3n/4 ≤ c·n for c = 3/4 < 1, so the condition holds.
Conclusion:
By case 3 of the Master theorem, T(n) = Theta(n).