GATE IT 2005 | Question: 51

Question

Let $T(n)$ be a function defined by the recurrence

$T(n) = 2T(n/2) + \sqrt n$ for $n \geq 2$ and
$T(1) = 1$

Which of the following statements is TRUE?

• A. $T(n) = \Theta(\log n)$
• B. $T(n) = \Theta(\sqrt n)$
• C. $T(n) = \Theta(n)$
• D. $T(n) = \Theta(n \log n)$

Comments

@piyushwm Your recursion tree is wrong. Check once again.

---

@gatecse @Abhrajyoti00 @Kabir5454

Somebody explain How( see comment of @piyushwm)

$\sqrt{2}^{logn} = \sqrt{n}$

and

In the gp , how you came to know that number of terms = logn not logn +1

---

(considering base of $logn$ is $2$) .

(1 --logn)-→ total logn terms.

(0—logn)→ total logn+1 terms 

 

Answer 1

T(n)=O(n)