An O(log n) Example
suggest changeIntroduction
Consider the following problem:
L is a sorted list containing n signed integers, for example [-5, -2, -1, 0, 1, 2, 4]. If L is known to contain zero, how can you find its index?
Naïve approach
The first approach that comes to mind is to inspect every element until zero is found. In the worst case, this takes n comparisons, so the time complexity is O(n).
This works for small values of n, but there is a more efficient approach.
Dichotomy
Consider the following binary search in Python 3:
def find_zero(values):
low = 0
high = len(values) - 1
while low <= high:
middle = (low + high) // 2
if values[middle] == 0:
return middle
if values[middle] < 0:
low = middle + 1
else:
high = middle - 1
raise ValueError("values does not contain zero")
low and high bound the part of the list that may contain zero. Each iteration inspects the middle element and discards half of the remaining search range.
In the worst case, the search continues until the range is empty. Because each iteration halves the remaining range, the time complexity is O(log n).
Explanation
When discussing binary search, log is naturally base 2. The base does not matter in Big-O notation because changing it multiplies the logarithm by a constant factor.
Let x be the number of halvings. The search ends when the remaining range has at most one element:
1 = n / 2^x, so 2^x = n and x = log₂ n.
Conclusion
When an algorithm repeatedly divides its remaining problem by a constant factor, its number of iterations is logarithmic.