Compare linear and binary searches

Question

I want to compare theoretical and practical ratios of linear search and binary search. It will be clear from my code, i hope:

import math
import random
import timeit


def linear_search(alist: list[int], elem: int) -> int | None:
    for item in alist:
        if item == elem:
            return elem
    return None


def binary_search(alist: list[int], elem: int) -> int | None:
    lo, hi = 0, len(alist) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if elem == alist[mid]:
            return elem
        elif elem < alist[mid]:
            hi = mid - 1
        else:
            lo = mid + 1
    return None


def compare_searches():
    # just some big value
    N = 100_000
    # just generate some sorted list 
    alist = [x for x in range(N)]
    # elem = random.randrange(N)
    # just some value to trigger the worst case scenarios during searches
    elem = -42

    # searches should give the same result
    assert linear_search(alist, elem) == binary_search(alist, elem)

    linear_time_avg = timeit.timeit(lambda: linear_search(alist, elem), number=10000)
    binary_time_avg = timeit.timeit(lambda: binary_search(alist, elem), number=10000)

    print("theoretical (complexities ratio): ", N / math.log2(N))

    print("practical (times ratio): ", linear_time_avg / binary_time_avg)


if __name__ == "__main__":
    compare_searches()

So this code produces:

theoretical (complexities ratio):  6020.599913279624
practical (times ratio):  898.7857719144624

I understand, that there should be some difference between complexities ratio and times ratio, but why is it so big? Like 6 times greater? I thought, that ratios will be roughfly the same tbh.

[What is big-O notation](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) — Mooing Duck, Aug 28 '23 at 14:42
The "theoretical" rate is meaningless, as it completely ignores coefficients and factors that have lesser degree, like constant factors. None of these are reflected in the complexity. Realise that O(1000N + 1000) == O(N). — trincot, Aug 28 '23 at 15:08
Time complexity describes the **growth** of a function, not the performance at any single point. In order to characterize the growth, you would need to measure the time taken at different input sizes *for a single algorithm*. Once you have those data points, you can fit a curve to them and that (ignoring constants) is the time complexity of that algorithm. Or at least that implementation of the algorithm. — beaker, Aug 28 '23 at 15:09

Mooing Duck · Answer 1 · 2023-08-28T15:24:50.743

Big-O notation is about how algorithms scale with size, and says almost nothing about their actual expected runtimes. This is why you're seeing a massive difference. Notably, a linear search like this is super fast for each iteration, because its so trivial, and your binary search is slower for each iteration, because it's doing math, and modifying variables.

your linear_search, for each iteration:

two comparisons
one addion/subtraction
no shifts
two potential branches.
no writes.

5 operations total, each taking different times, depending on a lot of complexities.

Your binary search, for each iteration:

three comparisons
two additions/subtractions
one shift (optimized division)
three potential branches
a write to a local variable (either lo or hi), which is fast, but will almost certainly cause a write-stall, since it immediately proceeds a comparison on those same two variables.

So the linear search is doing 100000 iterations, but only doing ~5 trivial ops per iteration. The binary search is ~17 iterations, but doing ~10 ops per iteration, and has a write-stall, so apparently each iteration is ~6.7 slower than that of the linear search.

From this, we can speculate the relative times of each of your algorithms are approximately T(N) vs T(6.7*log(N,2)), and therefore, the linear search is (slightly) faster for lists of less than about 32 items, and at around 32 items they're about the same speed, and then from there on, the binary search is faster. For lists with more than about 64 items, the binary search is rediculously faster.

Matrix multiplication is also a great example of this:

Schoolbook matrix multiplication requires O(N^3) multiplications, and is trivial, so is fast for tiny matrices with less than ~8 elements.
Most actual matrix multiplication libraries use Strassen's algorithm, which requires O(N^2.8074) multiplications, but it does require an extra ~11 additions and subtractions, which is constant overhead. For tiny matricies, these additions and subtractions might actually be slower than the schoolbook algorithm.
The Coppersmith–Winograd algorithm is only O(^2.373) multiplications, but requires so much constant-time work between each multiplication that it's actually slower than Strassen's for most matricies, and is only used for matrices with several hundred elements.
Williams, Xu, Xu, and Zhou's algorithm is only O(n^2.371552) multiplications, but these requires so much constant-time analysis between each multiplication that it was described by the authors as Galactic, and is therefore only actually faster if there are billions of elements in the matricies. But if you're multiplying matricies with trillions of elements, this algorithm would be the fastest.

Compare linear and binary searches

1 Answers1