Time Complexity Question about Square Roots

Question

I am trying to answer the following question:

Given n=2k find the complexity

func(n)

if(n==2) return1;

else n=1+func(sqrt(n))

end

I think because there is if-else statement, it will loop n times for sure, but I'm confused with the recursive loop for func(sqrt(n)). Since it is square-rooted, I think the time complexity would be

O(sqrt(n) * n) = O(n^1/2 * n) = O(n^3/2) = O(2k^3/2). However, the possible answer choices are only

1. O(k)
2. O(2^n)
3. O(n*k)

Can O(2k^3/2) be considered as O(k)? I'm confused because although time complexity is often simplified, O(n) and O(n^2) are different, so I thought O(2k^3/2) can only be simplified to O(k^3/2).

Answer 1

I’d argue that none of the answers here are the best answer to this question.

If you have a recursive function that does O(1) work per iteration and then reduces the size of its argument from n to √n, as is the case here, the runtime works out to O(log log n). The intuition behind this is that taking the square root of a number throws away half the digits of the number, roughly, so the runtime will be O(log d), where d is the number of digits of the input number. The number of digits of the number n is O(log n), hence the overall runtime of O(log log n).

In your case, you have n = 2k, so O(log log n) = O(log log k). (Unless you meant n = 2^k, In which case O(log log n) = O(log log 2^k) = O(log k).)

Notice that we don’t get O(n × √n) as our result. That would be what happens if we do O(√n) work O(n) times. But here, that’s not what we’re doing. The size of the input shrinks by a square root on each iteration, but that’s not the same thing as saying that we’re doing a square root amount of work. And the number of times that this happens isn’t O(n), since the value of n shrinks too rapidly for that.

Reasoning by analogy, the runtime of this code would be O(log n), not O(n × n / 2):

func(n):
    if n <= 2 return 1
    return func(n/2)