Let's take a quick review of all that we have learned about algorithms.
- We began by carefully defining
what an algorithm is. In our definition, we saw five important characteristics
that an algorithm must have:
- Algorithms are well-ordered.
- Algorithms have unambiguous operations.
- Algorithms have effectively computable operations.
- Algorithms produce a result.
- Algorithms halt in a finite amount of time.
- 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
- 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.
- 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
- 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).