The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
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

asked in Algorithms by Veteran (59.6k points)
edited by | 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)$

1 Answer

+15 votes
Best answer

Answer is $B$.

using master method (case 1)

where a = 2, b = 2

O(n1/2) < O(nlogba)

O(n1/2) < O(nlog22)

answered by Loyal (9.1k points)
edited by
Answer:

Related questions

0 votes
0 answers
5
asked Sep 29, 2014 in Non GATE by Kathleen Veteran (59.6k points) | 179 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,603 questions
48,602 answers
155,720 comments
63,760 users