The Gateway to Computer Science Excellence
+42 votes

Consider the following recurrence:

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

Which one of the following is true?

  1. $ T(n)=\Theta (\log\log n)$
  2. $ T(n)=\Theta (\log n)$
  3. $ T(n)=\Theta (\sqrt{n})$
  4. $ T(n)=\Theta (n)$
in Algorithms by Active (3.3k points)
edited by | 10k views
Using some substitutions along with applying master theorem answer seems to be O(logn). But i have a doubt. For n=2 ceil(sqrt(2)) will be 2 always. Since this will never converge, recurrence wont terminate. Any ideas what should be done here.
You are correct. It should be a mistake in question. Case 2 should have been specially mentioned.
hello, can you give the brief idea what's going in this recurrence ?
B. $\log n$
I am not clear what you are trying to say

If someone is getting confused in the  S(m) = 2S(m / 2) + 1  line in jatin's comment below,

then pls see below explanation,

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

=>Let , T(2m) = S(m)

=> 2T(2m / 22) + 1

=> 2S(m / 2) + 1 (2m == m & 22 == 2)






Thanks man , I got the point now.

Feeling a bit bad coz , it wasn't that hard but It's just how well u understood  THE SUBSTITUTION USED IN THE method.



Is this correct?


5 Answers

+45 votes
Best answer

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

by Veteran (431k points)
edited by

Put, $n=2^m$


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


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(2m) =  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.



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

Put, n=2^m




Using case 1 of master method ,


because of ,

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

logn = m log2

m = log n 

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
+11 votes

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


           $ =O(m)$

           $=O(log n)$
by Veteran (119k points)
edited by
√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...


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

+5 votes

asume n=2k and k=log n


asume T(2)=S(k)

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

use master theorm a=1 andb=2


T(n)=log log(n)

by (165 points)

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

+4 votes

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

by Boss (10.2k points)
+4 votes

Put, $n=2^m$




Using case 1 of master theorem,


SInce, $n=2^m$

$= \Theta(\log n)$
by Loyal (6.9k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,382 answers
105,323 users