GATE IT 2008 | Question: 44

Question

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

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

evaluates to :

• A. $√(n) (\log n + 1)$
• B. $√(n) \log n$
• C. $√(n) \log √(n)$
• D. $n \log √n$

Comments

//Assuming you have understood till this  ----> √(2^k) T(n/(2^k))+k√n    ---------- (*)

When does recursion stop?

       ---- when base case is reached i.e. T(1) in this case. //given T(1) = 1;

So, We have to turn T(n/(2^k)) into T(1).

---

How can we do that??

Viewpoint 1: 

If we put k = lg n, then we get , T(n/(2^lg n))       

By this ----->    property, we get 2^lg n = n          i.e. T(n/n) i.e. T(1).

Viewpoint  2:

 our aim is to substitute 2^k by n in T(n/(2^k)).

Let's do this substitution first, we get T(n/n) = T(1).

Now all we have to do is to find the value of k in terms of n.

                       2^k = n      // take lg

                 => k = lg n   

---

Thus, substituting value of k in (*) we get:

  √(2^log₂n) + log₂n √n

---

Then what's the use of condition n=2^2k mention in question?

---

Can it be solved using recursion tree method? Does the method work for a problem where the subproblem division is non-integral(like here sqrt(2))?

Answer 1

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

Answer 2

One long yet detailed way of doing this is using substitutions for matching parts:

Answer 3

using masters theorem we get

a =√2 b =2

n ^( log _b a)= n^ ( log ₂ √2 ) = n ^(1/2 log ₂ 2) = n ^1/2 =√n

f(n) = √n

So second rule of masters theorem applies

T(n) =θ(√n log n)

Comments

a/c to master theoram:

it should be θ(√n)

---

Could you please explain steps to get θ(√n)?

Answer 4

Answer is A