GATE CSE 2017 Set 2 | Question: 30

Question

Consider the recurrence function

$$T(n) = \begin{cases} 2T(\sqrt{n})+1, & n>2 \\ 2, & 0 < n \leq 2 \end{cases}$$

Then $T(n)$ in terms of $\Theta$ notation is

• A. $\Theta(\log \log n)$
• B. $\Theta( \log n)$
• C. $\Theta (\sqrt{n})$
• D. $\Theta(n)$

Comments

alternate method

n=0,1   T(0),T(1)=2

n=2   T(2)=2

now  T(4)=2*(T(2)+1 =5

       T(16)=2*5+1=11

       T(256)=2*11+1=23

       T(2^16) =2*23+1=47

       T(2^32)=2*47+1=95

      Log(2^32)=32 which lower bounds  95  so ans can  can;t be c or d   option a gives 5 which also lower bound 95  but as it is theta notation we go for tight bound

---

Hey plz help me why option b not option a .in the case of 2^32 valise from option 1 is theta(5) which can also be upper bounded by 95 as you said in your statement ?

Answer 1

$T(n)=2T({\sqrt{n}})+1$

Put, $n=2^m$ which implies $\sqrt n = n^{1/2} =2^{m/2}$

$\implies T(2^m)=2T(2^{m/2})+1$

put, $T(2^m) =S(m)$ which implies $T(2^{m/2}) = S(m/2)$

$\implies S(m)=2S(m/2)+1$

Using case 1 of master method ,

$=\Theta(m) = \Theta(\log n)$

 https://gateoverflow.in/1829/gate2006-51-isro2016-34?show=37791#c37791

Correct Answer: $B$

Comments

same concept ques was there in 2007, in that ques ans. was LogLog(n), Rzn: we are cutting the exponent of input by half.

DOUBT: WHY WE ARE CONSIDERING Log(n) HERE?

---

how do we know to put n= 2^k

---

@MadhavBansal It is intuitive like this:-

Suppose, $T(n) = aT(\sqrt[b]{n})+f(n)$ where $a>=1, b>1$

So, assume $[n=b^m → \sqrt[b]{n} = b^{m/b}]$

Thus, $T(b^m) = aT(b^{m/b}) + g(m)$

Then, assume $T(b^m) = S(m) → T(b^{m/b}) = S(m/b)$

So, $S(m) = aS(m/b) + g(m)$  // Apply Master Theorem now

Answer 2

Though $\sqrt{n}=2^m$ is the shortest method.

$T(n)=2T(n^{1/2}) +1$

$=2 *[ 2 T((n^{1/2})^{1/2}) +1] +1$

$=2^{2} T((n^{1/4}) +2 +1$

$=2^{3} T((n^{1/2^{3}}) +4 +2 +1$

$=2^{k} T((n^{1/2^{k}}) +2^{k-1}+ 2^{k-2}+..............+4 +2 +1$

$=2^{k} T((n^{1/2^{k}}) +[(2^{k}-1)/ 2-1] * 2^{0}$

---

as per given termination condition is $n^{1/2^{k}} =2$

$\Rightarrow log(n^{1/2^{k}}) =log(2)$

$\Rightarrow log(n) =2^{k}$

$\Rightarrow log( log(n)) =k$

---

inserting value of k or 2^k in above equation

$T(n)= log(n) * T(2) + log(n) - 1$

$T(n)= 3 log(n) - 1$

---

$T(n)= \Theta (log(n))$

Answer is B

Comments

inserting value of k or 2^k in above equation

T(n)=log(n)∗T(2)+log(n)−1

can you please explain this.

---

how we get this particular equation.

T(n)=log(n)∗T(2)+log(n)−1

---

this is the best explanation I found on youtube:: 

Answer 3

Hence answer is b.

Answer 4

hope it might help....

Comments

Thanku Dude