611 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 | 611 views
0
How to do it by recurrence tree method?
0

Recursion Tree Method :-

Here , $\frac{n^{\frac{1}{2}}}{(\sqrt{2}-1 )} * [(2^{k})^{\frac{1}{2}}\sqrt{2} - 1]$

Now , put $k = lgn$

$\Rightarrow \frac{n^{\frac{1}{2}}}{(\sqrt{2}-1 )} * [(2^{lgn})^{\frac{1}{2}}\sqrt{2} - 1]$

$\Rightarrow \frac{n^{\frac{1}{2}}}{(\sqrt{2}-1 )} * [(n)^{\frac{1}{2}}\sqrt{2} - 1]$

So , here , $T(n) = \frac{\sqrt{2}}{(\sqrt{2}-1)}*n - \frac{n^{\frac{1}{2}}}{(\sqrt{2}-1)}$

$\Rightarrow T(n) \leqslant c*n , where \; c> 0$

So, $T(n) = O(n)$

Answer is $B$.

using master method (case 1)

where a = 2, b = 2

O(n1/2) < O(nlogba)

O(n1/2) < O(nlog22)

edited

1
2