Is complexity O(log(n)) equivalent to O(sqrt(n))?

They are not equivalent: sqrt(N) will increase a lot more quickly than log2(N). There is no constant C so that you would have sqrt(N) < C.log(N) for all values of N greater than some minimum value.

An easy way to grab this, is that log2(N) will be a value close to the number of (binary) digits of N, while sqrt(N) will be a number that has itself half the number of digits that N has. Or, to state that with an equality:

        log2(N) = 2log2(sqrt(N))

So you need to take the logarithm(!) of sqrt(N) to bring it down to the same order of complexity as log2(N).

For example, for a binary number with 11 digits, 0b10000000000 (=210), the square root is 0b100000, but the logarithm is only 10.

Leave a Comment