# Basics: Algorithm

A kind reader pointed out that I frequently mention algorithms, but that I haven't defined them in the basics posts. To me, they're so fundamental to the stuff I do for a living that I completely forgot that they're an interesting idea.

It's really pretty simple: an algorithm is description of a mechanical procedure for performing a mathematical task. But that's actually a fairly sophisticated idea - the general concept of things that describe a procedure, and which can be discussed, described, and reasoned about as entities in their own right is something quite different from nearly anything that came before it.

The term algorithm has an interesting and humorous origin. Most people believe that it's named after a Persian mathematician named "Al-Khwarizmi". That's actually not quite true. While the term is derived from Al-Khwarizmi's name, it's actually an accident. In fact, what happened was that Al-Khwarizmi wrote a book about how to perform calculations using the Hindi numbering system (which is what we know as arabic numerals). Several hundred years later, the text was translated into Latin, and in the process of transliterating the name "Al-Khwarizmi" into Latin, the title of the book became "Algorithmi on Indian Numbers". "Algorithmi" looks like a latin plural noun - and so many European mathematicians interpreted the title of the book not as "Al-Khwarizmi talking about mathematical procedures using Indian numbers", but "Mathematical Procedures using Indian Numbers". And the term stuck.

So - an algorithm is a description mathematical procedure - and it's possible to reason about an algorithm as an entity itself. Let's look at a simple example, just to get the sense of it.

Suppose I have a list of N numbers in random order. I want to get the list into
increasing order - smallest first, largest last, ever number smaller than the number that comes after it.

One of the simplest algorithms for this is called bubble sort:

```Given: a list L1...LN of N numbers in random order.
Produce: a list of those N numbers in increasing order
Do:
repeat the following until the list no longer changes:
look at each pair of adjacent numbers Li and Li+1:
if Li > Li+1 then swap Li and Li+1```

This will produce a sorted list. Let's run through a quick example: the list [3,5,2,1,4].

1. First pass through the list:
1. Compare 3 and 5. 3<5 so move on to the next pair.
2. Compare 5 and 2. 5>2, so swap. List becomes [3,2,5,1,4]
3. Compare 5 and 1. 5>1, so swap. List becomes [3,2,1,5,4]
4. Compare 5 and 4. 5>4, so swap. List becomes [3,2,1,4,5]
2. The list changed, so we take another pass. Second pass:
1. Compare 3 and 2. 3>2, so swap. List becomes [2,3,1,4,5]
2. Compare 3 and 1.3>1, so swap. List becomes [2,1,3,4,5]
3. Compare 3 and 4. 3<4, so move on.
4. Compare 4 and 5. 4<5, so move on.
3. The list changed, so we do another pass. Third pass:
1. Compare 2 and 1. 2>1, so swap. List is now: [1,2,3,4,5].
2. Next four comparisons are (2,3), (3,4), (4,5), none of which cause swaps.
4. The list changed, so another pass. Fourth pass, everything is in order - each pair compares without causing changes. So the result is [1,2,3,4,5].

What can we say about this algorithm? Well, for one thing, it's slow. Given a list of N elements, we might need to do up to N passes over the list, each of which will do N-1 comparisons, each of which might cause a swap. So in the worst case, this will require N2-N comparisons and swaps to get the list into order. Our example wasn't even a worse case, and it ended up needed to do 16 comparisons (4 passes, 4 comparisons per pass), and 6 swaps. In the best case - the list is already in order - this algorithm will take one pass - N-1 comparisons, 0 swaps.

There are even some tricks using Kolmogorov-Chaitin information theory where we can show that on average, Bubble-sort will tend more towards the worse end of its possible performance than the best - but that's beyond the scope of a basics post, except to point out that we can apply interesting mathematical analyses to the algorithm itself to figure out what it's average performance should be, even without running it.

Tags

### More like this

##### Not Quite Basics: Sorting Algorithms
Multiple people have written to me, after seeing yesterday's href="http://scienceblogs.com/goodmath/2007/02/basics_algorithm_1.php">algorithms basics post, asking me to say more about sorting algorithms. I have to say that it's not my favorite topic - sorting is one of those old bugaboos that…
##### Zero
Back during the DonorsChoose fundraiser, I promised a donor that I'd write an article about the math of zero. I haven't done it yet, because zero is actually a suprisingly deep subject, and I haven't really had time to do the research to do it justice. But in light of the comment thread that got…
##### Basics: Binary Search
For the basics, I wrote a bunch of stuff about sorting. It seems worth taking a moment to talk about something related: binary search. Binary search is one of the most important and fundamental algorithms, and it shows up in sorts of places. It also has the amazing property that despite being…
##### Zero (classic repost)
I'm away on vacation this week, taking my kids to Disney World. Since I'm not likely to have time to write while I'm away, I'm taking the opportunity to re-run an old classic series of posts on numbers, which were first posted in the summer of 2006. These posts are mildly revised. This post…

Now that you have done a post on both algorithms and Turing Machines, you should do a post on Church's Thesis.

I enjoy your method of teaching Mark, I've been reading your blog for 3 months now (or so), always a nice read, especially the plonky ID drama! :)

Since the question was asked, my favourite algorithm is the Hopcroft state minimisation algorithm. It's one of the simplest algorithms which has the following properties:

1. What it does is easy to understand.

2. Writing a simple algorithm to solve the problem is easy, and it's easy to understand.

3. Taking one of the simplest algorithms, and making a very simple (a one line change in a typical programming language) modification to it, improves the running time from O(n^2) to O(n log n).

4. This modification is precisely the opposite of what you'd expect.

By Pseudonym (not verified) on 27 Feb 2007 #permalink

it's average performance

While I'm sure yesterdays human calculators were interested in how much time (how many operation) they used, I don't think they were much concerned with the number of papers. I have a feeling that computer science may have contributed with the complementary algorithm performance measure of needed memory space.

As someone who has a little programing experience (java), and understands the programing perspective of an algorithm, and the silliness that is a bubble sort, but has very basic math skills. Can you explain the difference between an algorithm used in programing, and an algorithm used in mathematics. Please excuse me if this seems odd, but my math skills suck. =( I'm working on it...

-- jolt

By joltvolta (not verified) on 27 Feb 2007 #permalink

The synchronicity of the web - speaking of performance measures, Jeffrey Shallit has a post where he relates his article to Spiked magazine on the "greatest innovation in my field":

In theoretical computer science, the greatest innovation is the realization that algorithms are mathematical objects, and can be rigorously analyzed in terms of their consumption of scarce resources, including space, time, and randomness.

Hmm. Randomness - is that a scarce resource due to the use of pseudorandom algorithms and/or finite number size? And if so, wouldn't that fall back to the constraints in time and space?

(Btw, every computer could easily have a circuit who gives good random numbers from a noise or quantum process - and it seems such circuits are WIP now.)

Hmm. Randomness - is that a scarce resource due to the use of pseudorandom algorithms and/or finite number size? And if so, wouldn't that fall back to the constraints in time and space?

I'm not quite what Shallit meant by that statement, but there are two distinct ways in which algorithms use randomness:

1.) Pseudoramdomness, which as you mention has some overlap with time and space. It however distinct due to it's use, for instance, as a statistical judgement of whether the output you get is "rigged" or not in randomized algorithms.

2.) Incompressibility: Turing machines are modeled with self-delimiting versions of their individual inputs bordered by "blanks", which goes back to the definition of "randomness" in Kolmogorov complexity, which is used to minimize redundancy.

It might be helpful to discuss a simple algorithm that people are familiar with, if you're trying to teach what an algorithm is in general. For instance, the algorithm that people use to multiply numbers of several digits (which is made possible by the use of arabic numerals), where you line up the numbers one above the other and multiply the digits, carrying the tens to the next column, etc.

I enjoyed learning sorts in computer science classes and comparing them to my own sorting algorithms. Many of them (but not heapsort!) had obvious analogues in my own behavior.

Randomness as a resource: Even on the idealized machines, the question of how many, say, uniformly random bits, you need for some algorithm is often an important question. Do I just need 4 random bits say, or do I need some number based on the size of the input. That is why it is looked at as a resource in the same way space or time are.

(Btw, every computer could easily have a circuit who gives good random numbers from a noise or quantum process - and it seems such circuits are WIP now.)

Intel had such a device, and included it on certain consumer-level Intel motherboards produced between 1999 and 2001. You may somewhere have a seven-year-old computer with a hardware random number generator in it.

It turned out that there wasn't really a need in most of what drives the consumer electronics market for a device - as of now, good-enough randomness is cheap even without such a hardware device.

Thanks Tyler, markk and Daniel for setting me straight:

It however distinct due to it's use, for instance, as a statistical judgement

Ah yes, Shallit may have meant it as a quality resource.

Even on the idealized machines, the question of how many, say, uniformly random bits, you need for some algorithm is often an important question.

I didn't think of use as an internal metric, but that makes sense too.

Intel had such a device, and included it on certain consumer-level Intel motherboards produced between 1999 and 2001.

Um, it was likely an old memory. I guess I should have checked the current situation first.

as of now, good-enough randomness is cheap even without such a hardware device

Glad to hear it. Considering the above remarks it seems I misread Shallit completely here.