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

algorithm time-complexity
white_tree picture white_tree · Feb 4, 2017 · Viewed 61.6k times · Source

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

trincot picture trincot · Feb 4, 2017

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

Related questions

How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More
What does O(log n) mean exactly?

I am learning about Big O Notation running times and amortized times. I understand the notion of O(n) linear time, meaning that the size of the input affects the growth of the algorithm proportionally...and the same goes for, …

Read More
How to find time complexity of an algorithm

The Question How to find time complexity of an algorithm? What have I done before posting a question on SO ? I have gone through this, this and many other links But no where I was able to find a clear …

Read More