Register

GATE IT 2008 | Question: 44

• edited by
31,265 views
117 117 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$

11 Answers

Best answer
176 176 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
48 48 votes
Answer: A
T(1) = 1 is given. Put n = 1 in all options. Only option A gives T(1) = 1.
40 40 votes

I have solved by both Master's theorem as well as iterative method. Option B is more accurate as they have mentioned "evaluates to".. they need the exact value which we could find via iterative method.

33 33 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$

22 22 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)

6 6 votes
As T(1) =1 , Checking if options are giving 1 at n=1:

A) giving 1

B),C),D) giving 0.
To be on safer side lets check for n=2:

T(2)=2 √2
(by putting n=2 in given recurrence)

by checking options we will find that only A) is giving 2 √2
Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE IT 2008 | Quest...Next → · GATE IT 2008 | Quest...
← Previous in category · GATE IT 2008 | Quest...Next in category → · GATE IT 2008 | Quest...
Position:
Show:

Related questions

23 23 votes
3 answers 3 answers
12.8k
12.8k views
Ishrat Jahan asked Oct 29, 2014
12,787 views
GATE IT 2008 | Question: 83
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); } }Which of the following im...
21 21 votes
5 answers 5 answers
12.0k
12.0k views
Ishrat Jahan asked Oct 29, 2014
12,018 views
GATE IT 2008 | Question: 82
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$...
32 32 votes
4 answers 4 answers
12.7k
12.7k views
Ishrat Jahan asked Oct 28, 2014
12,684 views
GATE IT 2008 | Question: 47
Consider the following sequence of nodes for the undirected graph given below:$a$ $b$ $e$ $f$ $d$ $g$ $c$$a$ $b$ $e$ $f$ $c$ $g$ $d$$a$ $d$ $g$ $e$ $b$ $c$ $f$$a$ $d$ $b$...
38 38 votes
5 answers 5 answers
23.2k
23.2k views
Ishrat Jahan asked Oct 28, 2014
23,175 views
GATE IT 2008 | Question: 45
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span­n...