edited by
17,772 views
47 votes
47 votes

Consider the recurrence function

$$T(n) = \begin{cases} 2T(\sqrt{n})+1, & n>2 \\ 2, & 0 < n \leq 2 \end{cases}$$

Then $T(n)$ in terms of $\Theta$ notation is

  1. $\Theta(\log \log n)$
  2. $\Theta( \log n)$
  3. $\Theta (\sqrt{n})$
  4. $\Theta(n)$
edited by

6 Answers

Best answer
69 votes
69 votes

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

Put, $n=2^m$ which implies $\sqrt n = n^{1/2} =2^{m/2}$

$\implies T(2^m)=2T(2^{m/2})+1$

put, $T(2^m) =S(m)$ which implies $T(2^{m/2}) = S(m/2)$

$\implies S(m)=2S(m/2)+1$

Using case 1 of master method ,

$=\Theta(m) = \Theta(\log n)$

 https://gateoverflow.in/1829/gate2006-51-isro2016-34?show=37791#c37791

Correct Answer: $B$

edited by
34 votes
34 votes

Though $\sqrt{n}=2^m$ is the shortest method.

$T(n)=2T(n^{1/2}) +1$

$=2 *[ 2 T((n^{1/2})^{1/2}) +1] +1$

$=2^{2} T((n^{1/4}) +2 +1$

$=2^{3} T((n^{1/2^{3}}) +4 +2 +1$

$=2^{k} T((n^{1/2^{k}}) +2^{k-1}+ 2^{k-2}+..............+4 +2 +1$

$=2^{k} T((n^{1/2^{k}}) +[(2^{k}-1)/ 2-1] * 2^{0}$


as per given termination condition is $n^{1/2^{k}} =2$

$\Rightarrow log(n^{1/2^{k}}) =log(2)$

$\Rightarrow log(n) =2^{k}$

$\Rightarrow log( log(n)) =k$


inserting value of k or 2^k in above equation

$T(n)= log(n) * T(2) + log(n) - 1$

$T(n)= 3 log(n) - 1$


$T(n)= \Theta (log(n))$

Answer is B

Answer:

Related questions

41 votes
41 votes
4 answers
1
Arjun asked Feb 14, 2017
20,976 views
A message is made up entirely of characters from the set $X=\{P, Q, R, S, T\}$. The table of probabilities for each of the characters is shown below:$$\begin{array}{|c|c|...
50 votes
50 votes
7 answers
2
Madhav asked Feb 14, 2017
24,347 views
Consider the following C functionint fun(int n) { int i, j; for(i=1; i<=n; i++) { for (j=1; j<n; j+=i) { printf("%d %d", i, j); } } }Time complexity of $fun$ in terms of ...
29 votes
29 votes
5 answers
3
Madhav asked Feb 14, 2017
7,931 views
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the ...
25 votes
25 votes
7 answers
4
khushtak asked Feb 14, 2017
6,794 views
Match the algorithms with their time complexities:$$\begin{array}{|l|l|}\hline \textbf{Algorithms} & \textbf{Time Complexity} \\\hline \text{P. Tower of Hanoi with $n$...