I’m not complex, I’m linear

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.
This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s