edited by
17,118 views
73 votes
73 votes

When $n = 2^{2k}$ for some $k \geqslant 0$, the recurrence relation

$T(n) = √(2) T(n/2) + √n$, $T(1) = 1$

evaluates to :

  1. $√(n) (\log n + 1)$
  2. $√(n) \log n$
  3. $√(n) \log √(n)$
  4. $n \log √n$
edited by

9 Answers

Best answer
112 votes
112 votes

$T(n) = \sqrt(2) T\left(\frac{n}{2}\right) + \sqrt n$
           $= {\sqrt 2}^2 T\left(\frac{n}{2^2} \right) +\sqrt {2} \sqrt {\frac{n}{2}} + \sqrt n$
           $\vdots$
           $= {\sqrt 2}^ {\lg n} T(1) +\lg n \sqrt n$
           $=\sqrt n + \lg n \sqrt n$
           $= \sqrt n \left( \lg n + 1\right)$

If we use Master theorem we get option B. But one must know that Master theorem is used to find the asymptotic bound and not an EXACT value. And in the question here it explicitly says "evaluates to".

edited by
29 votes
29 votes
Answer: A
T(1) = 1 is given. Put n = 1 in all options. Only option A gives T(1) = 1.
17 votes
17 votes

Using Master's Theorem,  Option B is coming

But solving the recurrence equation using back substitution, Option A is coming

As, they have not used Theta notation in the answer, so I am assuming they want the exact solution.

Therefore Answer is (A)

13 votes
13 votes

$T(n)=\sqrt2\ T\left ( \dfrac{n}{2} \right )+\sqrt{n}$

                            $\downarrow$

$\sqrt{2}\left (\sqrt{2}\ T\left ( \dfrac{n}{2^2} \right )+\sqrt{\dfrac{n}{2}} \right )+\sqrt{n}$

$(\sqrt{2})^2\ T\left ( \dfrac{n}{2^2} \right )+\sqrt{n}+\sqrt{n}$

.

.

.

$(\sqrt{2})^k\ T\left ( \dfrac{n}{2^k} \right )+k\sqrt{n}$

$\dfrac{n}{2^k}=1$

$k=log_{2}n$

$(\sqrt{2})^{log_{2}n}\ T\left ( \dfrac{n}{2^{log_{2}n}} \right )+log_{2}n\sqrt{n}$

$\sqrt{n}\ T\left ( 1 \right )+log_{2}n\sqrt{n}$

$\sqrt{n}(1+log_{2}n)$


$Ans:A$

Answer:

Related questions

15 votes
15 votes
4 answers
2
Ishrat Jahan asked Oct 29, 2014
9,156 views
Consider the code fragment written in C below :void f (int n) { if (n <=1) { printf ("%d", n); } else { f (n/2); printf ("%d", n%2); } }What does f(173) print?$010110101$...