The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- $O(n)$
- $O(\log n)$
- $O(\log \log n)$
- $O(1)$

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.8k
- Algorithms 3.3k
- Theory of Computation 4.1k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1.1k
- Others 1.4k
- Admissions 496
- Exam Queries 443
- Tier 1 Placement Questions 19
- Job Queries 59
- Projects 9

37,111 questions

44,694 answers

127,231 comments

43,753 users