An Example of an Algorithm

Suppose you are given an unsorted list of numbers and want to find the largest number in this list.

• How do you do it?
• Do you have to look at every number in the list?
• Might you have to look at each number more than once?
• Is there a best or optimal way to do it?
• How do we measure how much work a computer must do when using an algorithm?

Here's an informally described algorithm:

1. When you begin, the first number is the largest number in the list you've seen so far.
2. Look at the next number, and compare it with the largest number you've seen so far.
3. If this next number is larger, then make that the new largest number you've seen so far.
4. Repeat steps 2 and 3 until you have gone through the whole list.

Given: a list of numbers "list" 

largest = list[1]
counter = 2
while counter <= length(list)
    if list[counter] > largest
        largest = list[counter]
    counter = counter + 1
print largest

Are their other algorithms for solving this general problem?

• Sure: Sort the list of numbers and then pick the one at the end of the list.
• This is obviously not as good as the first algorithm.

It's easy to prove that:

• Any algorithm has to look at every number.
• You only have to look at each number once
• If we measure the work in terms of a basic operation of <i> comparing one number with another</i> then finding the largest of N numbers takes N-1 steps
• So we can prove that our algorithm is optimal, in general