PA of Algorithms Q44

44Let 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?

Option : C
Explanation :
T(n) = 2T(n/2) + √n
Apply master’s method
n^log₂² ⇒ n > √n
So T(n) = Θ(n)

Forgot your password?

I agree with the Terms.