edited by
27,766 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

Best answer
58 votes
58 votes

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

edited by
31 votes
31 votes
$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)$
edited by
16 votes
16 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)$
edited by
6 votes
6 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)

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,698 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 \...