edited by
27,756 views
58 votes
58 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)$
edited by

7 Answers

4 votes
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

2 votes
2 votes

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

 

0 votes
0 votes
we can do this question by one more way.

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

 

Here, if a recursion program would be formed from this relation then, returning statement would be

return √n+√n +c( any other constant) which becomes 2T(√n) + c

for example, if we take n=8 then √8=2√2 whose ceiling value is 3 and ceiling value is also mentioned in the question.

and log8 base 2 =3

therefore  Θ(log n)
Answer:

Related questions

17 votes
17 votes
2 answers
3
go_editor asked Jul 6, 2016
9,057 views
For the real time operating system, which of the following is the most suitable scheduling scheme?Round robinFirst come first servePre-emptiveRandom scheduling
64 votes
64 votes
15 answers
4
Arjun asked Jul 6, 2016
36,697 views
Consider the following segment of C-code:int j, n; j = 1; while (j <= n) j = j * 2;The number of comparisons made in the execution of the loop for any $n 0$ is:$\lceil \...