What is the time complexity of the next function?

Question

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

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

• About (1)
• O (log n)
• O (lg lg n)
• O (n)

I think the running time is completely dependent on sqrt (n). However, I do not know how this function is actually implemented.

PS A general approach to finding the square root of a number that I know of is using Newton's method. If I am not mistaken, the complexity of time using the Newton method is equal to O (log n). So, should there be an O (log n) answer?

PPS Got this question in a recent test in which I appeared.

Answer 1

I am going to give a slightly more general answer without assuming a constant size int.

Theta(logn).

, Newton-raphson - Theta (logn) - Theta(n) (, sqrt() , ).

n log_2(n) - , sqrt(). Theta(1) Theta(log(log(n)).

, Theta(log(n)).

, O(log(n)) O(n) - , . O .

Answer 2

sqrt, , .

, "", O (1) : int, . (: ).

. O (M (n)), M (n) - , n - .

, , , . , , , sqrt ( O (n)) ( O (1)).

, "" , .