[Solved] Time Complexity of Binary Search?

Question

With binary search you typically search in a sorted random access data structure like an array, by discarding half of the array with each comparison. Hence, in k steps you effectively cover 2^k entries. This yields a complexity of at most log2(n) of n elements.

With landau symbols, the base of the logarithm disappears because it is a constant: O(log2(n)) = O(log(n) / log(2)) = O(log(n)).

Now, if you, for some reason, can not only discard half of the values, but two thirds, by always knowing in which third the needle will end up in, this means you cover 3^k many entries in k steps.

Hence, you get log3(n). But this again reduces to the same time complexity as log(3) is a constant: O(log3(n)) = O(log(n)/log(3)) = O(log(n)).

Accepted Answer

With binary search you typically search in a sorted random access data structure like an array, by discarding half of the array with each comparison. Hence, in k steps you effectively cover 2^k entries. This yields a complexity of at most log2(n) of n elements.

With landau symbols, the base of the logarithm disappears because it is a constant: O(log2(n)) = O(log(n) / log(2)) = O(log(n)).

Now, if you, for some reason, can not only discard half of the values, but two thirds, by always knowing in which third the needle will end up in, this means you cover 3^k many entries in k steps.

Hence, you get log3(n). But this again reduces to the same time complexity as log(3) is a constant: O(log3(n)) = O(log(n)/log(3)) = O(log(n)).