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?

- $ T(n)=\Theta (\log\log n)$
- $ T(n)=\Theta (\log n)$
- $ T(n)=\Theta (\sqrt{n})$
- $ T(n)=\Theta (n)$

+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

+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(2^{m}) = 2T(2^{m/2}) + 1

=>Let , *T*(2^{m}) = *S*(*m*)

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

=> 2S(m / 2) + 1 (2^{m} == m & 2^{2} == 2)

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

+110

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

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

+8

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

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

$2^{\log \log n}T(2)+2^{\log \log n} -1$

How this is $\Theta( \log n )$ ?

+8

@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$.

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

+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 ..!

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

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)

+1

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

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

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

+11 votes

+5 votes

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)

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,382 answers

198,529 comments

105,323 users