11,171 views

## 5 Answers

Best answer

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**

### 5 Comments

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

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)

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)

### 4 Comments

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)

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)

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)

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)