570 views

Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$.

Which of the following statements is true?

1. $T(n) = O \sqrt{n}$

2. $T(n)=O(n)$

3. $T(n) = O (\log n)$

4. None of the above

edited | 570 views
0
How to do it by recurrence tree method?

Answer is $B$.

using master method (case 1)

where a = 2, b = 2

O(n1/2) < O(nlogba)

O(n1/2) < O(nlog22)

edited