What Is an Algorithm

You are keeping score at a quiz night. Five teams finish with 4, 9, 2, 11 and 6 points. Who won? You glance at the numbers and say "11" in about a second.

Now there are 3,000 teams. Or a new helper has to find the winner without you, and get it right every time. Glancing no longer works. You need to write down exactly what your eyes did. That written-down method is an algorithm.

#Write down what you did

Slow down and watch yourself find the highest score. You probably did something like this:

1. Look at the first score and remember it. Call it the best so far.
2. Look at the next score. If it is bigger than the best so far, it becomes the new best so far. Otherwise, ignore it.
3. Repeat step 2 until there are no scores left.
4. The best so far is the answer.

That is a complete algorithm. It is short, but it works for 5 teams or 5 million, and anyone who follows it gets the same answer you did. A computer can follow it too, which is the point: a computer only does exactly what it is told.

#What makes it an algorithm

A cooking recipe is often called an algorithm, and it is close. But a recipe says things like "bake until golden" or "a pinch of salt". A person can judge that. A computer cannot. An algorithm has to be stricter:

• Clear input and output. Here the input is a list of scores and the output is one number, the highest.
• Every step is exact. "Is this score bigger than the best so far?" has a yes or no answer. "Pick the one that looks biggest" does not.
• It finishes. Each repeat of step 2 uses up one score, and the list is not endless, so you always reach step 4.
• It is right for every valid input, not only the example you tried first.

#Trace it by hand

Before writing any code, run the steps yourself on the quiz scores. Doing this with a pencil is the single best habit you can build. Click through and watch the best so far change.

if there are no scores: there is no winnerbest = the first scorefor each later score s:  if s > best:    best = sanswer: best

Notice the sentence that stayed true the whole way: "best is the highest score among the ones I have looked at." It is true after the first score. Each step keeps it true. So when you have looked at all of them, best must be the highest of all. That sentence is what lets you trust the method on inputs you never tried.

#The same steps in code

Code is the algorithm written in a language a computer can run. Each line below matches a line of the plain-English version.

function highestScore(scores) {
  if (scores.length === 0) return null; // no scores, no winner
  let best = scores[0];                 // the first score is the best so far
  for (let i = 1; i < scores.length; i++) {
    if (scores[i] > best) {
      best = scores[i];                 // found a new best
    }
  }
  return best;
}
 
highestScore([4, 9, 2, 11, 6]); // 11

def highest_score(scores):
    if not scores:
        return None  # no scores, no winner
    best = scores[0]  # the first score is the best so far
    for i in range(1, len(scores)):
        if scores[i] > best:
            best = scores[i]  # found a new best
    return best
 
highest_score([4, 9, 2, 11, 6])  # 11

Both languages have this built in (Math.max(...scores) in JavaScript, max(scores) in Python). Under the hood they do the same walk. Writing it yourself once means you know what the built-in costs.

#Does it always work

One example passing proves very little. Try inputs that are designed to break things:

• Winner first: [11, 4, 9]. Best starts at 11 and never changes. Correct.
• Winner last: [4, 9, 11]. Best changes on the very last step. Correct.
• A tie: [9, 11, 11]. The second 11 is not bigger than 11, so best stays 11. Correct.
• Only one team: [7]. The loop never runs and the answer is 7. Correct.
• Penalty points: [-3, -1, -7]. Best starts at −3, becomes −1. Correct.
• No teams: []. There is no first score to start with, so the first line returns null (None in Python) before anything else runs.

Small, awkward inputs like these are called edge cases. Checking them is part of writing the algorithm, not an extra.

#How much work it does

With n scores, the method makes n − 1 comparisons. Twice as many teams, twice the work. That is about as good as it gets for this problem: any score you skip might be the winner, so every one must be looked at once.

The badges use Big-O notation, which the next lesson explains properly. For now read O(n) as "work grows in step with the number of items".

#Same problem, better algorithm

Two correct algorithms for the same problem can do wildly different amounts of work. Say you want to find the name "Okafor" in a printed list of 1,000,000 names in alphabetical order. You could check every name from the top: up to 1,000,000 looks. Or you could open the list in the middle, see whether "Okafor" comes before or after that name, and throw away the half it cannot be in. Repeat. Each look halves what is left, so about 20 looks are enough.

Same input, same answer, but about 20 looks instead of 1,000,000. Gaps like that are what studying algorithms is about. The halving trick is called binary search, and it only works because the list is sorted. Finding the highest score in an unsorted list has no such shortcut.

#Common mistakes

#Check yourself

#What to practise next

You counted comparisons by hand to see how much work the method does. Big-O Notation turns that counting into a quick way to compare any two algorithms before you run them.