Consider the recurrence relation : \(\begin{array}{} T(n)& =8T \bigg(…
2017
Consider the recurrence relation :
\(\begin{array}{} T(n)& =8T \bigg( \dfrac{n}{2} \bigg) + Cn, \text{if } n>1 \\ & =b, \text{if } n=1 \end{array}\)
Where b and c are constants. The order of the algorithm corrosponding to above recurrence relation is :
- A.
\(n\) - B.
\(n^2\) - C.
\(n \lg n\) - D.
\(n^3\)
Attempted by 209 students.
Show answer & explanation
Correct answer: D
Given: T(n) = 8 T(n/2) + Cn, with T(1) = b.
Identify parameters: a = 8, b = 2, and f(n) = Theta(n).
Compute n^{log_b a}: n^{log_2 8} = n^3.
Compare f(n) to n^{log_b a}: f(n) = Theta(n) = O(n^{3 - 2}) (take epsilon = 2), so f(n) is polynomially smaller than n^3.
Conclusion: By case 1 of the Master Theorem, T(n) = Theta(n^3).
Intuition: the recursion tree has height log_2 n.
Number of leaves is 8^{log_2 n} = n^{log_2 8} = n^3, and the work is dominated by these leaves, yielding Theta(n^3).