GATE CSE 1997 | Question: 4.6

Question

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?

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

• B. $T(n)=O(n)$

• C. $T(n) = O (\log n)$

• D. None of the above

Comments

@ankitgupta.1729 the height in your recurrsion tree it should be Log(n)  I think not Log(n) +1, take n = 16 and trace the tree its height is 4 i.e. Log(16) 

---

@arpit.jha both log(n) and log(n)+1 are correct. You can take any one of them which you like.

There is no single definition of height of a tree.

---

ok sir

Answer 1

Answer is $B$.

using master method (case $1$)

where $a = 2, b = 2$

$O(\sqrt{n}) < O(n^ {log_b a})$

$O(\sqrt{n}) < O(n^{log_2 2})$

$O(\sqrt{n}) < O(n^1)$

Comments

Here $\mathrm{k \ngeq 0}$, then how you applied Master's theorem?

---

@Satbir

Do you think this selected answer even correct?

---

k is 0.5

---

Ohh..that was a foolish mistake.

Thanks.

Answer 2

n^(log2 2)=n

f(n)=√n

n^(log2 2) is polynomially greater then f(n)

Extended Master's theorm CASE 1:

f(n)=O(n^(logb a)-e) e>0,then T(n)=Θ(n^logb a)

T(n)=Θ(n) Option B

Comments

@theradash u can use $fx$  for functions  to  make ur ans good use latex equations