GATE CSE 2002 | Question: 2.11

Question

The running time of the following algorithm

Procedure $A(n)$

If $n \leqslant 2$ return ($1$) else return $(A( \lceil  \sqrt{n}  \rceil))$;

is best described by

• A. $O(n)$
• B. $O(\log n)$
• C. $O(\log \log n)$
• D. $O(1)$

Comments

how to solve this question..?

---

https://math.stackexchange.com/questions/538268/can-you-help-me-to-solve-the-recurrence-relation-tn-t-sqrt-n-1

Answer 1

$Ans:C$

---

$T(n) = T(\sqrt n)  + c$

Assume $n=2^k$

$T(2^k)=T(2^{k/2})+c$

Assume $T(2^k)=S(k)$

$S(k)=S(k/2)+c$

Apply Master Theorem

$S(k)=\Theta(1.\log\ k)$

Now just do the reverse

$T(2^k)=\Theta(\log\ k)$

Now replace with $k=\log_{2}n$

$T(2^{\log_{2}n})=\Theta(\log(\log_{2}n))$

$T(n)=\Theta(\log(\log_{2}n))$

Answer 2

We will solve this question using recursive tree method

Answer 3

Let us replace $ n = 2^{\log{n}} $

$ A(2^{\log{n}}) $

$= A(2^{\frac{\log{n}}{2}}) + c$

$= A(2^{\frac{\log{n}}{4}}) + 2c$
…………
….……..
$= A(2^{\frac{\log{n}}{2^{k}}}) + kc$
…………
In order to get base value i.e A(2) in our equation,

$ 2^{\frac{\log{n}}{2^{k}}} = 2$

$ \frac{\log{n}}{2^{k}} = 1$

$ \log{n} = 2^{k} $

$ k = \log{\log{n}} $

substituting the value of k with our derivation,

$A(n)\ = A(2) + c\log{\log{n}} = Θ(\log{\log{n}})\  $

$[\ A(2)\ and\ c\ are\ constants,\ we\ can\ ignore\ them\ asymptotically\ ]$