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.

Answer 2

This depends on the implementation of sqrt and also on what kind of time complexity you are interested.

I would say you can consider it to be "constant", so O(1), in that sense: If you put in a random int, it will in average take the same amount of time. (Reason: numbers with many digits are much more common).

But have a look here. Another possible answer is O(M(n)), where M(n) is the complexity of a multiplication and n is the number of digits in your integer.

This looking like a text-book question and a is perhaps meant to be a trap. The teacher perhaps wants to check if you can distinguish between computing sqrt for a list of numbers (which would be O(n)), and a single number (which would be O(1)).

Be aware that the "correct" answer often also depends on the context in which it is asked.