11,171 views

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)$

how to solve this question..?

### Subscribe to GO Classes for GATE CSE 2022

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)$

by

why is it +1 and not some constant c in recurrence relation
why we are adding constant in recurrence relation?
because u will do some constant amount of work at every recurrence

Read this article once, then you may not need to solve this again ever, it becomes very intuitive.

https://stackoverflow.com/questions/16472012/what-would-cause-an-algorithm-to-have-olog-log-n-complexity

@Hemant Parihar why this is not following O(lognlogn) complexity though problem is diveded into √n each time?

https://gateoverflow.in/197521/recurrence-relation

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)
by

How you write S(m/2) please tell me i don't understand...

@69akki  let s(m)=T(2^.m)

now in S of m  put m=m/2 than you will get your answer

now the reduced is of the form

T(m)=aS(m/b) +1

here a=1.,b=2, k=1 and p=0 right ?

applying ...

a<b^k  then case 3 of 1 will come in master's theorem

if so ans will be T(m)=O(m^k logm^P)

here p=0 , the term Logm^P becomes 1

remainig term is O(m), then it is O(logn )

please some one explain how O(loglogn)
@teluguenglish You wrote k = 1 which is wrong, k should be 0 as 1 = n^0.

Then you will get S(m) = O(logm) by extended master's theorem.

As n = 2 ^ m, we will get m = log n.

Then T(n) = S(m) = log(m) = log(log(n)) = loglogn.
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)

### 1 comment

log log n.
substitute root n = m then proceed.

$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))$