If I divide array size by 3 what will the running time of Binary search.
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)).
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments