GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
604 views

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?

  1. $T(n) = \Theta(\log n)$
  2. $T(n) = \Theta(\sqrt n)$
  3. $T(n) = \Theta(n)$
  4. $T(n) = \Theta(n \log n)$
asked in Algorithms by Veteran (20.8k points)  
recategorized by | 604 views
Is the question ok?
I am getting D, after subsituting values for different numbers.
can someone solve this qus by using recursion TREE!!!?

1 Answer

+13 votes
Best answer
Option C it can be done by Master theorem.

$n^{\log_b a} = n^{\log_2 2} = n$.

$f(n) = \sqrt n = n^{\frac{1}{2}}$.

So, $f(n) = O\left(n^{\log_b a -\epsilon}\right)$ is true for any real $\epsilon$, $0 < \epsilon < \frac{1}{2}$. Hence Master theorem Case 1 satisfied,
$$T(n) = \Theta\left(n^{\log_b a}\right) = \Theta (n).$$
answered by Veteran (13.3k points)  
selected by
this is not in aT(n/b) +n power k log n .

How can this be one in ny Master's?
master theorem /...how!!1!
How?
There was a typo in question. Corrected now.
Thanks!
Answer:

Related questions



Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2070 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,648 answers
79,695 comments
31,069 users