Official PYQ · 2002Q2.11Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2002 Q2.11 — Asymptotic Worst Case Time and Space Complexity

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

View worked solution

Answer: C

To find the running time of the procedure $A(n)$ , we can write its recurrence relation. Let $T(n)$ be the time complexity of the algorithm for an input size $n$ :

T(n) = T\left(\lceil \sqrt{n} \rceil\right) + \Theta(1) \quad \text{for } n > 2

To solve this recurrence, we can ignore the ceiling function for asymptotic analysis and use the change of variables method.

Let $n = 2^k$ , which implies $k = \log_2 n$ . Substituting this into the recurrence:

T(2^k) = T\left((2^k)^{1/2}\right) + c = T(2^{k/2}) + c

Let $S(k) = T(2^k)$ . The recurrence relation becomes:

S(k) = S\left(\frac{k}{2}\right) + c

Applying the Master Theorem (Case 2) or by simple expansion, we get:

S(k) = \Theta(\log k)

Now, substituting $k = \log_2 n$ back into the solution:

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

Thus, the running time of the algorithm is best described by $O(\log \log n)$ .

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Asymptotic Worst Case Time and Space Complexity questions

GATE CS 2002 Q2.11 — Asymptotic Worst Case Time and Space Complexity

Related questions