Let T(n) be defined as T(1) = 1 and T(n) = 2T(floor(n/2)) + sqrt(n) for n >=…
1997
Let T(n) be defined as T(1) = 1 and T(n) = 2T(floor(n/2)) + sqrt(n) for n >= 2. Which of the following statements is true?
- A.
T(n) = O(sqrt(n))
- B.
T(n) = O(n)
- C.
T(n) = O(log n)
- D.
None of the above
Attempted by 8 students.
Show answer & explanation
Correct answer: B
The recurrence is T(n) = 2T(floor(n/2)) + sqrt(n). For asymptotic order, the floor does not change the result.
Using Master theorem: a = 2, b = 2, so n^(log_b a) = n^(log_2 2) = n. The extra work is f(n) = sqrt(n), which is polynomially smaller than n.
Therefore the recurrence falls under Master theorem Case 1, and T(n) = Theta(n). Hence T(n) = O(n), so option B is true.