An O(log n) Example

suggest change

Introduction

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.

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents