Let's take a quick review of all that we have learned about algorithms.

  1. We began by carefully defining what an algorithm is. In our definition, we saw five important characteristics that an algorithm must have:


    1. Algorithms are well-ordered.
    2. Algorithms have unambiguous operations.
    3. Algorithms have effectively computable operations.
    4. Algorithms produce a result.
    5. Algorithms halt in a finite amount of time.

  2. We discussed three different ways to represent algorithms: plain English, programming languages, and structured English. We found that plain English was too wordy and ambiguous for specifying algorithms. On the other hand, programming languages require knowledge of many details that are not relevant to algorithms. Our compromise was to use structured English to represent algorithms.

  3. We learned three different sorting algorithms: the Simple Sort, the Insertion Sort, and the Selection Sort. We found that these algorithms actually provide a solution to a class of problems. They are useful not only for sorting cards, but also for names, numbers, dates, etc.

  4. We compared the space efficiency and the time efficiency of the three sorting algorithms. Although the Selection Sort was the most efficient sort in our example, we found that these results can change depending on the number of items sorted and the order of the items. To perform a better comparison, we found formulas that describe the performance of our sorting algorithms in the worst case.

  5. We compared the efficiency formulas of the sorts and introduced the idea of order notation. We discovered that the performance of an algorithm depends heavily upon the size of the largest term in the efficiency formula. In order notation, this term defines what class an algorithm belongs to. Four common classes of algorithms are O(log n), O(n), O(n2), and, O(2n).