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

Question

My professor just taught us that any operation that halves the length of the input has an O(log(n)) complexity as a thumb rule. Why is it not O(sqrt(n)), aren't both of them equivalent?

Answer 1

They are not equivalent: sqrt(N) will increase a lot more quickly than log₂(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 log₂(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:

? ? ? ? log₂(N) = 2log₂(sqrt(N))

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

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