edited by
17,728 views
47 votes
47 votes

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

  1. $O(n)$
  2. $O(\log n)$
  3. $O(\log \log n)$
  4. $O(1)$
edited by

7 Answers

Best answer
65 votes
65 votes

The complexity will be the number of times the recursion happens which is equal to the number of times we can take square root of n recursively, till n becomes $2$.

$T(n) = T\left(\lceil \sqrt n \rceil \right) + 1$

$T(2) = 1$
$T\left(2^2\right) =  T(2) + 1 = 2$
$T\left(2^{2^2}\right) =  T(4) + 1 = 3$
$T\left(2^{2^3}\right) =  T(16) + 1 = 4$

So, $T(n) = \lg\lg n + 1 = O\left(\log \log n\right)$

Answer Option C

edited by
28 votes
28 votes
T(n)=T(sqrt(n))+1

We substitute n=2^m. Then T(2^m)=T(2^m/2) +1

we substitute T(2^m)=S(m).

S(m)=S(m/2)+1.

Now applying masters theoram we get S(m)=O(log m). As m=logn.

T(n)=O(log log n)
15 votes
15 votes
Another way to solve this is:

T(n) = T(n^1/2)+c

T(n) = T(n^1/4)+c+c

T(n) = T(n^1/8)+c+c+c

T(n) = T(n^1/16)+c+c+c+c

................

.........

...........

T(n) = T(n^(1/2^k))+k.c

So, n^(1/2^k) = 2

taking log will give us:-      log(n) = 2^k--------------futher taking log --------- k =loglogn

T(n) = T(2)+loglogn . c

so , ans will be C) O(loglogn)
Answer:

Related questions

35 votes
35 votes
2 answers
1
Kathleen asked Sep 15, 2014
11,773 views
The solution to the recurrence equation $T(2^k) = 3T(2^{k-1})+1, T(1) =1$ is$2^k$$\frac{(3^{k+1}-1)}{2}$$3^{\log_2 k}$$2^{\log_3 k}$