My son got some homework from school connected to common multiples of two integers. For a while I couldn’t remember what this meant – until I remembered the least common multiple. This made me remember the rather clever proof using lcm to deduce that the partial sums of the harmonic series
1 + 1/2 + 1/3 + … + 1/n
aren’t integer after the first term.
On the way to work I started thinking through some linear algorithms that surprised me when I first heard about them.
The Majority Vote algorithm discovered and proved by Boyer and Moore in 1980. Given a sequence of votes, if we know that there is a candidate with a majority, we can find it in a single linear scan. They proved the algorithm using the Boyer-Moore theorem prover, a theorem prover that was designed to prove things inductively across a computational logic based on Lisp.
Finding loops in a path in linear time using tortoise and hare algorithm, that can be used to solve problems like this.
Finding the median of a collection of numbers in worst case linear time.
Searching for a substring match in super-linear time.