1,086 views
4 votes
4 votes

For the following program fragment, the running time is given by

Procedure A(n) 
{
    if(n <= 2) 
        return 1; 
    else return A(log (n)); 
}
  1. $\Theta(\log \log n)$
  2. $\Theta(\log \sqrt n)$
  3. $\Theta(\log^* n)$
  4. $\Theta(\sqrt n)$

2 Answers

Best answer
6 votes
6 votes

$T(n) = T(\log n) + 1$

Solution to this recurrence is : no of times logrithmic function applied on $n$ in order to get base condition, which is nothing but $\log^* n$.

Complexity $=\Theta (\log ^*n)$

selected by
1 votes
1 votes

Let's take some values of n.

Clearly, the recurrence is  $T(n)=T(logn)+1$

I'll take it as $T(n)=T\left \lceil (logn) \right \rceil+1$ because $logn = O\left \lceil (logn) \right \rceil$


n = $1024$

$1024\rightarrow 10\rightarrow 4\rightarrow 2$

3 recursive calls.

So, for 1024, it is $O(loglogn)$


n = $2^{2048}$

$2^{2048}\rightarrow 2048\rightarrow 12\rightarrow 4\rightarrow 2$

4 recursive calls.

So, for $2^{2048}$ it is $O(logloglogn)$


n = $2^{2^{2^{2048}}}$

$2^{2^{2^{2048}}}\rightarrow $ $2^{2^{2048}}\rightarrow $ $2^{2048}\rightarrow 2048\rightarrow 12\rightarrow 4\rightarrow 2$

6 recursive calls.

So, for $2^{2^{2^{2048}}}$ it is $O(loglogloglogn)$


 

It is evident that number of logs is dependent upon how big the input value is. So, it would be Option C

Answer:

Related questions

2 votes
2 votes
1 answer
2
Bikram asked Oct 4, 2016
327 views
The Matrix Chain-Product dynamic programming Algorithm runs in _______linear timeexponential timequadratic timecubic time
3 votes
3 votes
1 answer
4
Bikram asked Oct 4, 2016
499 views
Let we have 3 steps of an arbitrary program fragment whose running times are $O(n^2), \: O(n^3)$ and $O(n\log n)$, then the running time of whole program is$O(n^3)$$\Omeg...