c++ - What is the time complexity of the following function?

Question

    int func(int n){
       if(n==1)
         return 0;
       else
         return sqrt(n);
    }

Where sqrt(n) is a C math.h library function.

1. O(1)
2. O(lg n)
3. O(lg lg n)
4. O(n)

I think that the running time entirely depends on the sqrt(n). However, I don't know how this function is actually implemented.

P.S. The general approach towards finding the square root of a number that I know of is using Newton's method. If I am not wrong, the time complexity using Newton's method turns out to be O(lg n). So should the answer be O(lg n)?

P.P.S. Got this question in a recent test that I appeared for.

Answer 1

I am going to give a bit more general case answer, without assuming constant size of int.

The answer is Theta(logn).

We know newton-raphson is Theta(logn) - that excludes Theta(n) (assuming sqrt() is as efficient as we can).

However, a general number n requries log_2(n) bits to encode - and you require to read all of it in order to get an accurate sqrt() function. This excludes Theta(1) and Theta(log(log(n)).

From the above, we know that the complexity of the function is Theta(log(n)).

As a side note, since O(log(n)) is a subset of O(n) - it is also a valid answer, though not tight one. For more information about big Theta and big O and their differences, you might want to have a look on this thread.