##### Example on Finding Complexity

Find the complexity of the below function :

int function(int n){
if(n <= 2) return 1;
else return(function(floor(sqrt(n))) + 1);
}

(A) $O(\log\log n)$
(B) $O(\log n)$
(C) $O(n\log n)$
(D) $O(n^2\log n)$

Let us write the recurrence first.

$T(n) = T(\sqrt n) + c$

So we can see that recurrence relation depends on operation if we consider the non recursive part not the operands itself.

So if in the program , it were written, $return(\ function (floor(\sqrt n) ) + n^2)$, then many of us would have written,

$T(n) = T(\sqrt n) + n^2$

But it is wrong. We should concentrate on the fact we are doing just one addition with n and hence as we know the basic arithmetic operations take constant time , so the recurrence relation would not change in this case as well.
Now coming back to the question ,

$T(n) = T(\sqrt n) + c$

Let $n = 2^k$.Then recurrence can be rewritten as:

$S(k) = S( k/2) + c$

which on solving gives $O(\log k)$ by Master's Theorem.
But $k = \log n$.
Hence                                                                                     $T(n) = O(\log k) = O(\log \log n)$.
Hence (A) option is correct.