Searching and Big-O

Two ways to search

To find something in a list, the obvious method is linear search: check the first item, then the next, and so on. If the item is last, or missing, that’s every item checked.

If the list is sorted, there’s a much better way. Binary search checks the middle item. If that’s too small, the target can only be in the upper half, so the lower half is discarded; if it’s too big, the upper half goes. Each check halves what’s left, so for n items it needs at most about log₂ n checks ¹. It’s how you’d look up a word in a paper dictionary, or guess a number between 1 and 100 when told “higher” or “lower.”

This program counts the checks each method makes to find the last item. Save it as search.py:

# search.py: count the comparisons linear search and binary search make.

def linear_search(items, target):
    """Check each item in turn."""
    for count, item in enumerate(items, start=1):
        if item == target:
            return count
    return len(items)

def binary_search(items, target):
    """Items must be sorted. Check the middle, then throw away the half that can't hold target."""
    lo, hi, count = 0, len(items) - 1, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        count += 1
        if items[mid] == target:
            return count
        if items[mid] < target:
            lo = mid + 1                # target is in the upper half
        else:
            hi = mid - 1                # target is in the lower half
    return count

for n in (1_000, 1_000_000, 10_000_000):
    items = range(n)                    # sorted, and indexable without storing every number
    target = n - 1                      # the last item: the worst case for a linear search
    print(f"n = {n:>10,}   linear: {linear_search(items, target):>10,} checks   binary: {binary_search(items, target):>2} checks")

lo and hi mark the part of the list that could still hold the target; each pass through the loop moves one of them past the middle.

me@linuxbox:~$ python3 search.py
n =      1,000   linear:      1,000 checks   binary: 10 checks
n =  1,000,000   linear:  1,000,000 checks   binary: 20 checks
n = 10,000,000   linear: 10,000,000 checks   binary: 24 checks

Multiplying the data by ten thousand took binary search from 10 checks to 24.

Logarithms

The logarithm base 2, log₂ n, answers: how many times can you halve n before you get down to 1 ¹? log₂ 1,000 is about 10, log₂ 1,000,000 about 20, and log₂ 1,000,000,000 about 30. Doubling n adds just one to it. That’s why anything that halves its problem at each step, binary search, a balanced search tree, scales so well.

Big-O

Counting exact steps is hopeless: the real time depends on the machine, the language, and a dozen constants nobody knows ¹. Big-O notation keeps only how the time grows with the size of the input, n. A function f(n) is O(g(n)) if, for all large enough n, f(n) is at most some constant times g(n) ¹. In practice that means: keep the fastest-growing term and drop constant factors. A running time of 5n log n + 8n − 200 is O(n log n) ¹.

The common classes, from best to worst ¹:

The differences get enormous. This program prints the step counts for a few sizes. Save it as growth_table.py:

# growth_table.py: how many steps each kind of algorithm takes as n grows.
import math

print(f"{'n':>9}  {'log2 n':>6}  {'n log2 n':>12}  {'n^2':>17}  {'2^n':>12}")
for n in (10, 100, 1_000, 1_000_000):
    print(f"{n:>9,}  {math.log2(n):>6.1f}  {round(n * math.log2(n)):>12,}  {n * n:>17,}  "
          f"{'about 10^' + str(round(n * math.log10(2))):>12}")

me@linuxbox:~$ python3 growth_table.py
        n  log2 n      n log2 n                n^2           2^n
       10     3.3            33                100    about 10^3
      100     6.6           664             10,000   about 10^30
    1,000    10.0         9,966          1,000,000  about 10^301
1,000,000    19.9    19,931,569  1,000,000,000,000  about 10^301030

At a billion simple steps a second, a million items take: about 20 nanoseconds at O(log n), a millisecond at O(n), 0.02 seconds at O(n log n), and 1,000 seconds, nearly 17 minutes, at O(n²) ¹. At O(2ⁿ), even n = 100 would take about 40 trillion years.

Big-O is a statement about large n. If two algorithms have different big-O, the one with the smaller growth wins once n is big enough; if they have the same big-O, only measuring tells you which is faster, and the answer may differ between machines ¹. An O(n) algorithm taking 15n steps loses to an O(n log n) one taking 2n log₂ n steps until n passes about 181 ¹, and then wins by more and more.

Worst case and average case

Big-O usually describes the worst case, unless it says otherwise. Linear search’s worst case is n checks; on average, for a target that’s present, it’s about n/2, which is still O(n). Some structures are quoted by their average case: a dict lookup is O(1) on average and O(n) in the worst case, when every key collides ². Last module’s binary search tree was the same story: about 12 visits among 1,000 random keys, 500 on average for sorted ones.

The doubling test

You can often read an algorithm’s growth straight from its timings: run it at size n, then at 2n, and compare. Here are three ways to ask “is x here?” timed at three sizes. Save it as doubling.py:

# doubling.py: double n and watch how each kind of lookup's time changes.
import time
from bisect import bisect_left

def per_lookup(fn, repeats):
    start = time.perf_counter()
    for _ in range(repeats):
        fn()
    return (time.perf_counter() - start) / repeats * 1e6      # microseconds

print(f"{'n':>10}  {'x in list':>12}  {'bisect':>9}  {'x in set':>9}   (microseconds)")
for n in (1_000_000, 2_000_000, 4_000_000):
    items = list(range(n))
    as_set = set(items)
    x = n - 1
    scan = per_lookup(lambda: x in items, 20)                  # O(n)
    halve = per_lookup(lambda: bisect_left(items, x), 100_000) # O(log n)
    hashed = per_lookup(lambda: x in as_set, 100_000)          # O(1)
    print(f"{n:>10,}  {scan:>12.1f}  {halve:>9.3f}  {hashed:>9.3f}")

On a desktop PC:

me@linuxbox:~$ python3 doubling.py
         n     x in list     bisect   x in set   (microseconds)
 1,000,000        3038.5      0.120      0.029
 2,000,000        6201.4      0.109      0.029
 4,000,000       12243.7      0.121      0.047

The list scan doubles each time: O(n). Binary search barely moves, since doubling n adds one check to about twenty: O(log n). The set stays tiny: O(1), give or take some noise from the memory hierarchy. The general rule:

Last module’s list.insert(0, x) loop went from 1.0 to 3.9 seconds when n doubled: four times, so the whole loop was O(n²).

Binary search in practice

Python’s bisect module does binary search on sorted lists. bisect_left(a, x) returns the position where x would go to keep a sorted, which is also where x is if it’s present ³. The module’s documentation shows how to build exact lookups from it ³:

from bisect import bisect_left

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

Binary search needs sorted data, and keeping data sorted has its own cost; that’s next lesson. And you’ve used binary search before: git bisect (Git course) finds the commit that introduced a bug by testing the commit halfway between a known good one and a known bad one, then halving again ⁴. A thousand commits take about ten tests.

Your turn

So

Linear search checks every item, O(n); binary search halves sorted data at every check, O(log n): 24 checks for ten million items. Big-O keeps how an algorithm’s time grows and drops constants and smaller terms; the classes run O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), and the gaps between them dwarf any difference in hardware. Big-O usually means the worst case. The doubling test reads growth from timings: double n, and see whether the time stays put, steps up, doubles, or quadruples.