##### 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^{2 } 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.