Algorithm

In mathematics and computer science an algorithm (the word is derived from the name of the Persian mathematician Al-Khwarizmi) is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state (contrast with heuristic). Algorithms can be implemented by computer programs, although often in restricted forms; mistakes in implementation and limitations of the computer can prevent a computer program from correctly executing its intended algorithm.

Example

One of the simplest algorithms is to find the largest number in an (unsorted) list of numbers. The solution necessarily requires looking at every number in the list, but only once at each. From this follows a simple algorithm:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• Look at each item in the list. If it is larger than any that has been seen so far, make a note of it.
• The latest noted item is the largest in the list.

And here is a more formal coding of the algorithm in pseudocode:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Algorithm LargestNumber

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Input: A non-empty list of numbers L.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Output: The largest number in the list L.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

largest ← -∞

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

for each item in the list L, do

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

if the item > largest, then

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

largest ← the item

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

return largest

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Notes on notation:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• "←" is a loose shorthand for "changes to". For instance, with "largest ← the item", it means that the largest number found so far changes to this item.
• "return" terminates the algorithm and outputs the value listed behind it.

As it happens, most people who implement algorithms want to know how much of a particular resource (such as time or storage) a given algorithm requires. Methods have been developed for the analysis of algorithms to obtain such quantitative answers; for example, the algorithm above has a time requirement of O(n), using the big O notation with n as the length of the list. At all times the algorithm only needs to remember a single value; the largest number found so far. Therefore this algorithm has a space requirement of O(1). (Note that the size of the inputs is not counted as space used by the algorithm.)

Related Topics:
Analysis of algorithms - Big O notation

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For a more complex example see Euclid's algorithm.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~