in Algorithms edited by
11,171 views
37 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)$
in Algorithms edited by
11.2k views

2 Comments

how to solve this question..?
4

Subscribe to GO Classes for GATE CSE 2022

5 Answers

56 votes
 
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

edited by
by

5 Comments

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

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

10

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

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

1
20 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)

4 Comments

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

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

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

1
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)
0
@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.
0
13 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)

1 comment

1
11 votes
log log n.
substitute root n = m then proceed.
3 votes

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

 

edited by
Answer:

Related questions