What is an algorithm? An algorithm is a procedure to accomplish a specific task. It is the idea behind any computer program.
To be interesting, an algorithm has to solve a general, well-specified problem. An algorithmic problem is specified by describing the complete set of instances it must work on and what properties the output must have as a result of running on one of these instances. This distinction between a problem and an instance of a problem is fundamental. For example, the algorithmic problem known as sorting is defined as follows:
Input: A sequence of n keys 
.
Output: The permutation (reordering) of the input sequence such that
.
An instance of sorting might be an array of names,
such as {Mike, Bob, Sally, Jill, Jan}, or a list of numbers like
{154, 245, 568, 324, 654, 324}.
Determining whether you in fact have a general problem to deal with,
as opposed to an instance
of a problem, is your first
step towards solving it.
This is true in algorithms as it is in life.
An algorithm is a procedure that takes any of the possible input instances and transforms it to the desired output. There are many different algorithms for solving the problem of sorting. For example, one method for sorting starts with a single element (thus forming a trivially sorted list) and then incrementally inserts the remaining elements so that the list stays sorted. This algorithm, insertion sort, is described below:
InsertionSort(A)
for i = 1 to n-1 do
for j = i+1 to 2 do
if (A[j] < A[j-1]) then swap(A[j],A[j-1])
Note the generality of this algorithm. It works equally well on names as it does on numbers, given the appropriate < comparison operation to test which of the two keys should appear first in sorted order. Given our definition of the sorting problem, it can be readily verified that this algorithm correctly orders every possible input instance.
In this chapter, we introduce the desirable properties that good algorithms have, as well as how to measure whether a given algorithm achieves these goals. Assessing algorithmic performance requires a modest amount of mathematical notation, which we also present. Although initially intimidating, this notation proves essential for us to compare algorithms and design more efficient ones.
While the hopelessly ``practical'' person may blanch at the notion of theoretical analysis, we present this material because it is useful. In particular, this chapter offers the following ``take-home'' lessons:
grows very slowly with increasing n.