The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 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)$
asked in Algorithms by Veteran (52k points)
edited by | 3.4k views
how to solve this question..?

4 Answers

+41 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

answered by Veteran (407k points)
edited 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.


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

+11 votes
log log n.
substitute root n = m then proceed.
answered by Veteran (59.8k points)
+6 votes

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

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


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

T(n)=O(log log n)
answered by Active (4.1k points)
+3 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)
answered by Junior (697 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,120 answers
71,034 users