Consider the following recurrence relation. \(T\left ( n \right…
2021
Consider the following recurrence relation.
\(T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.\)
Which one of the following options is correct?
- A.
\(T(n)=\Theta (n^{5/2})\) - B.
\(T(n)=\Theta (n\log n)\) - C.
\(T(n)=\Theta (n)\) - D.
\(T(n)=\Theta ((\log n)^{5/2})\)
Attempted by 72 students.
Show answer & explanation
Correct answer: C
Recurrence: T(n) = T(n/2) + T(2n/5) + 7n, with T(0) = 1.
Work per level and geometric decay:
Root level work: 7n.
At the next level, the two subproblems have total size n/2 + 2n/5 = (1/2 + 2/5)·n = 0.9·n, so their combined non-recursive work is 7·0.9·n.
By induction, level k contributes 7n·(0.9)^k.
The total non-recursive work is the geometric series 7n · sum_{k>=0} (0.9)^k = 7n / (1 - 0.9) = 70n = Θ(n).
Conclusion: T(n) = Θ(n).
Alternative justification (Akra–Bazzi): solve for p with (1/2)^p + (2/5)^p = 1, which gives p ≈ 0.87 < 1. Since the non-recursive term is f(n) = Θ(n) = Θ(n^{1}) and 1 > p, Akra–Bazzi yields T(n) = Θ(n).
A video solution is available for this question — log in and enroll to watch it.