GATE CSE 2006 | Question: 51, ISRO2016-34

Question

Consider the following recurrence:

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

Which one of the following is true?

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

Comments

Thank you !

---

Substitution method : 2 Types

1)

\[
\begin{array}{ccc}
T(n) & & T(n-1) \\
\downarrow & & \downarrow \\
\text{1 : } S(2^n) & & S(2^{n-1}) \\
& 2^n = m & \\
\text{2 : } S(m) & & S(m/2)
\end{array}
\]

Refer : https://gateoverflow.in/460070/gate-cse-2025-set-1-question-10?show=460325#a460325

---

2)

\[
\begin{array}{ccc}
T(n) & & T(\sqrt{n}) \\
\downarrow & & \downarrow \\
& n = 2^m & \\
\text{1 : } T(2^m) & & T(2^{m/2}) \\
\text{2 : } S(m) & & S(m/2)
\end{array}
\]

Refer : https://gateoverflow.in/1829/gate-cse-2006-question-51-isro2016-34?show=319474#a319474

---

Done ✅

Answer 1

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

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

           $ = 4\times T\left(n^{\frac{1}{2^2}}\right) + 5 $

           $ = 8\times T\left(n^{\frac{1}{2^3}}\right) + 13 \\ \cdots$

           $=2^{(\lg \lg n)} + 2 \times \lg \lg n  + 1\text{ (Proved below)} $

           $= \Theta(\lg n)$

---

$n^{\frac{1}{2^k}} = 2 \\ \text{(Putting 2 so that we can take log.}\\\text{One more step of recurrence can't change the complexity.)} \\\implies \frac{1}{{2^k}} \lg n = 1 \text{(Taking log both sides)}\\\implies \lg n = 2^k \\\implies k = \lg \lg n$

So, answer is B, $T(n) = \Theta(\log n)$

Comments

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

Put, $n=2^m$

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

put,$T(2^m) =s(m)$

$s(m)=2s(m/2)+1$

Using case 1 of master method ,

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

---

@asu what is correct answer here ?

---

it is B, both methods are fine - it was marked wrongly as A.

---

$\begin{align*} \\ T(n) & =2T(\sqrt{n}) +1 \\ & =2T(n^{\frac{1}{2}})+1 \\ & = 4T(n^{\frac{1}{4}})+3 \\ & = 8T(n^{\frac{1}{8}})+ 7 \\ & = 2^{k} T(n^{\frac{1}{2^{k}}})+ (2^{k} -1 ) \end{align*}$

When we put  $k= \log \log n$

$2^{\log \log n}T(2)+2^{\log \log n} -1$
How this is $\Theta( \log n )$  ?

---

@Arjun sir
I think u have missed 2 in the first step pls check that

---

Thanks. Corrected..

---

@Dulqar since $\alpha^{log_{\alpha}x} = x$, we get $2^{log_{2}log_{2}n} + T(2) + 2^{log_{2}log_{2}n}-1= log_2n + T(2) + log_2n - 1$

Constants are ignored, and we are left with $log_2n$.

---

But in Official Key of ISRO, answer is Option A

---

I'm getting same answer- option (b), but my second last step is different. Please someone guide me where am I getting wrong?

---

@jatin_saini, are you sure, according to your method  i am getting O(n), can you show your procedure once ..!

---

here que case 2 ie,T(1)=1 is given as wrong so T(2)=1 is correctone, now you could get the ans

---

How you got O(n).

You can check procedure above.

---

How to get that m/2 after substituting T(2^m) =  S(m)

---

i get Θ(n) then how you got log n using master theoram step 1. plz explain this i am confusing only last step.

---

I am not getting the second last step of the solution , how T(n ^ (1/2^k)) becomes equal to T(1) as it will be possible only when T(1)=2, but it is given in question that T(1)=1.

---

@dharmesh7

T(n)=2T(√ n )+1   

Put, n=2^m

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

put,T(2^m)=s(m)

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

Using case 1 of master method ,

=Θ(m) 

because of ,

 n = 2^m (take log both of the side )

logn = m log2

m = log n 
so
=Θ(logn)

---

thanks

---

Can anyone please tell regarding Jatin solution, what is the approach and how to think to substitute n = $2^{m}$

---

What does T(2^m)=S(m) mean? Why cant it be T(2^m)=T(p) by putting 2^m=p ?

---

$T(2^m)$ and  $S(m)$  are just functions...

$T(2^m)$  is function of m, replaced by $S(m)$

$T(2^{m/2})$  is a function of $m/2$ , which is replaced by  $S(m/2)$.

---

I am having difficulty to understand how such substitution works.Can you please elaborate it?
Also,Is there any other way to do it?

---

You can do it as it is done in selected answer

---

(Putting 2 so that we can take log.One more step of recurrence can't change the complexity.)

I think this statement is wrong because it requires a lot more than”one” recurrence step to square root 2 till it becomes 1. sqrt(2) =1.414 not 1. sqrt(1.414)=1.189 and so on. There seems to be no upper bound on the number of steps of recurrences required to square root 2 till it becomes 1. And since for every step the cost of recurrence step becomes 2x the previous step, the resultant complexity of this question doesn't seem to have any upper bound. If you look closely everyone has changed the question as per their choice and assumed T(2)=1 or T(3)=1. This is misleading i think.

 

 

---

Given: T(n) = 2T(√n) + 1 n → √n → n^(1/4) → n^(1/8) → ... If we assume: T(2) = 1 is a valid base case for obtaining: Then answer is Θ(log n) But here given T(1) = 1 problematic? If we use: T(1) = 1 we would need: n^(1/2^k) = 1 Therefore, the recursion never reaches 1 in a finite number of steps. So, for: T(n) = 2T(√n) + 1 the intended valid case assumption is usually: T(1) = 1 Hence, the expected answer is: T(n) = Θ(loglog n)

Answer 2

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

Put, $n=2^m$

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

$T(log2^m)=2T(log2^{m/2})+c$

$T(m)=2T(m/2)+c$

Using case 1 of master theorem,

$=\Theta(m)$

SInce, $n=2^m$

$= \Theta(\log n)$

Comments

How are you getting 4^th step: T(log(2^m)) = 2T(log(2^(m/2)))+c

 

That doesnt tally with the original recurrence equation:  T(n)=2T(√n)+1

because you have taken n =log(2^m) then T(n) = 2T(√(log(2^m)))+1

Answer 3

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

          $ =2T(2m)+1$    $n=2^{m}$ , $m=log n$

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

           $ =O(m)$

           $=O(log n)$

Comments

√n=2^m then m=log n

Logic is not clear.

---

see jatin saini's answer. He applied correct logic.

srestha , your answer is correct but i doubt if procedure and logic correct too...

---

@srestha 

It should be  $n=2^m$,  not $\sqrt n=2^m$

Answer 4

$Ans:B$

---

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

Assume $n=2^k$

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

Assume $T(2^k)=S(k)$

$S(k)=2S(k/2)+1$

Apply Master Theorem

$S(k)=\Theta(k)$

Now just do the reverse

$T(2^k)=\Theta(k)$

Now replace with $k=log_{2}n$

$T(2^{log_{2}n})=\Theta(log_{2}n)$

$T(n)=\Theta(log_{2}n)$

 

Answer 5

asume n=2^k and k=log n

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

asume T(2^k )=S(k)

now S(k)=s(k/2)+1

use master theorm a=1 andb=2

T(2^k)=logk

T(n)=log log(n)

Comments

It is not right solution,bcoz 2 is miss in the equation.

Right equation is , S(k)= 2s(k/2)+1

By Master theorem  ,S(k)= k

then T(n)= logn

Hence ans is B) logn

Answer 6

Unrolling the recursion,

T(n)  =  2T(n^(1/2)) + 1
=  2^2T(n^(1/4)) + 2
= 2^3T(n^(1/8)) + 3
.
.    k  steps
.
=  2^kT(n^(1/2k)) + k              …………. (1)

Using the Base case,

n^(1/2k) = 2
Taking log on both sides
log2n = 2k
k = log2log2n

From (1),

T(n) =  log2n  +  log2log2n
= Theta(log2n)

Here log2n : log(base 2) n

Comments

I think your eq. 1 is wrong

It should be -> T(n) = 2^kT(n^(1/2^k))+2^k-1+2^k-2+.....+2²+2+1