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

Option B

put n=2^m

T(2^m)=2T(2^m/2) + 1

put (2^m)=S(m)

S(m)=2S(m/2)+1

=Theta(m)=Theta(logn)-------Masters Thm

Answer 2

https://gateoverflow.in/?qa=blob&qa_blobid=18088847482472950234