Question

The running time of the following algorithm procedureA(n)
If n < = 2 return (1) else return (A($\lceil$$\sqrt{n}$ $\rceil$)); is best described by

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

Answer 1

The correct option is A O(log log n)

Recursive relation for procedure A(n) is
T(n) = T($\sqrt{n}$) + c1 if n > 2
Let n = $2^m$
$\Rightarrow$ T(n) = T($2^m$)
$\Rightarrow$ T($2^m$) = S(m)
$\Rightarrow$ T(n) = S(m)
$\Rightarrow$ T($\sqrt{n}$) = T($2^{m/2}$) = S(m/2)
T(n) = T($\sqrt{n}$) + c1 is n > 2
$\therefore$ S(m) = S($\frac{m}{2}$) + c1
= O(log m)
= O(log log n) [$\therefore$ n= $2^m$ $\Rightarrow$ m = log m]
$\Rightarrow$ T(n) = S(m)
= O(log log n)
$\therefore$ Option (c) is correct.