The solution of the recurrence relation \(T(m) = T(3m/4)+1\) is
2018
The solution of the recurrence relation \(T(m) = T(3m/4)+1\) is
- A.
\(\Theta (\lg \: m)\) - B.
\(\Theta (m)\) - C.
\(\Theta (m\lg m)\) - D.
\(\Theta (\lg\lg m)\)
Attempted by 112 students.
Show answer & explanation
Correct answer: A
Solution overview: derive the recurrence depth and total cost.
At depth i the problem size is (3/4)^i * m.
Recursion stops when (3/4)^k * m ≤ 1, so k = log_{4/3} m, which is Θ(log m).
Each level contributes a constant +1, so the total T(m) is Θ(k) = Θ(log m).
Final answer: T(m) = Θ(log m).
A video solution is available for this question — log in and enroll to watch it.