The Gateway to Computer Science Excellence
+38 votes
9.4k views

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 | 9.4k views
+6
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.
+3
You are correct. It should be a mistake in question. Case 2 should have been specially mentioned.
0
hello, can you give the brief idea what's going in this recurrence ?
+1
B. $\log n$
0
I am not clear what you are trying to say
+1

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)

 

 

 

 

0

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.

0

 

Is this correct?

0
Correct!

5 Answers

+44 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 (425k points)
edited by
+103
$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)$
0
@asu what is correct answer here ?
+3
it is B, both methods are fine - it was marked wrongly as A.
+7
$\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 )$  ?
+1
@Arjun sir
I think u have missed 2 in the first step pls check that
0
Thanks. Corrected..
+7
@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$.
+1
But in Official Key of ISRO, answer is Option A
+2

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

0
@jatin_saini, are you sure, according to your method  i am getting O(n), can you show your procedure once ..!
+1
here que case 2 ie,T(1)=1 is given as wrong so T(2)=1 is correctone, now you could get the ans
0
How you got O(n).

You can check procedure above.
+1

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

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

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.

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

0
thanks
+1
Can anyone please tell regarding Jatin solution, what is the approach and how to think to substitute n = $2^{m}$
0
What does T(2^m)=S(m) mean? Why cant it be T(2^m)=T(p) by putting 2^m=p ?
+1
$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)$.
0
I am having difficulty to understand how such substitution works.Can you please elaborate it?
Also,Is there any other way to do it?
0
You can do it as it is done in selected answer
+9 votes
$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)$
by Veteran (117k points)
edited by
+1
√n=2^m then m=log n

Logic is not clear.
0
see jatin saini's answer. He applied correct logic.

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

@srestha 

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

+5 votes

asume n=2k and k=log n

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

asume T(2)=S(k)

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

use master theorm a=1 andb=2

T(2k)=logk

T(n)=log log(n)

by (165 points)
0

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 (10k points)
+1 vote
$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)$
by Active (2.6k points)
edited ago 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,645 questions
56,578 answers
195,771 comments
101,769 users