Ben Carter

$O(n)$ does not mean fast. It means the running time grows at most linearly as $n$ grows. A $O(n)$ algorithm can lose to a $O(n^2)$ one on small inputs. Constants matter.

Binary search runs in $O(\log n)$ time, but the off-by-one bugs are famous. lo, hi = 0, len(a) while lo < hi: mid = (lo + hi) // 2 if a[mid] < target: lo = mid + 1 else: hi = mid The invariant: the an