Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + √n for n ≥ 2…
2005
Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + √n for n ≥ 2 and T(1) = 1 Which of the following statements is TRUE?
- A.
T(n) = θ(log n)
- B.
T(n) = θ(√n)
- C.
T(n) = θ(n)
- D.
T(n) = θ(n log n)
Attempted by 121 students.
Show answer & explanation
Correct answer: C
Apply the Master Theorem to the recurrence T(n) = 2T(n/2) + √n.
Identify parameters: a = 2, b = 2, and f(n) = n^{1/2}.
Compute n^{log_b a} = n^{log_2 2} = n.
Compare f(n) with n^{log_b a}: f(n) = n^{1/2} = O(n^{1 - 1/2}) so f(n) = O(n^{log_b a - ε}) with ε = 1/2.
By the Master Theorem (case 1), T(n) = Θ(n^{log_b a}) = Θ(n).
Recursion-tree intuition: the cost at level i is 2^{i}·√(n/2^{i}) = √n · 2^{i/2}. Summing levels up to log n gives Θ(n). The leaves contribute Θ(n) as well, so total cost is Θ(n).
Final answer: T(n) = Θ(n).
A video solution is available for this question — log in and enroll to watch it.