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

 

 

Answer

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.

0Comment