In the last lesson, we discovered that we can represent the efficiency of our sorting algorithms with formulas. We derived these formulas by identifying the most important operations in the algorithm (e.g. comparisons, copies, or swaps) and then counting how many of these operations were required to sort a specific number of items. Next, we found a general pattern in the number of operations required at each step and used this pattern to write our formula. One such formula that we derived was the formula to describe the number of comparisons the Simple Sort requires in the worst case. The formula is given below.
# of comparisons = n
* (n-1) |
Since the largest term in this formula is n^{2}, we discovered that the number of comparisons needed grows very quickly. We also saw a couple other formulas whose largest term was n, and we found these formulas only showed moderate growth. From these examples, we can see that the size of the largest term in an algorithm's efficiency formula has a very great effect on the performance of an algorithm. In fact, algorithms are classified based on the size of this term. This classification is called "order notation" and it is used to compare the amount of work that different algorithms must perform to do the same job. An algorithm which has n^{2} as its highest term would be called an O(n^{2}) algorithm (pronounced "order-n-squared algorithm"). An algorithm with n as its highest term would be called an O(n) algorithm (pronounced "order-n algorithm"). Two other common classes of algorithms are O(2^{n}) and O(log n). The graph below shows you how the performance of these four classes of algorithms compares.
Although we used sorting algorithms to introduce the idea of efficiency and order notation, these ideas apply to all algorithms. For example, suppose we wrote a search algorithm to find a telephone number in a large list of phone numbers. We could also describe the efficiency of this algorithm using order notation. In this case, n would represent the size of phone directory (i.e. the number of phone numbers). The most important operation in this algorithm would be comparing numbers, so we would be interested in knowing how many comparisons our algorithm would need to find a particular phone number. If our algorithm is efficient, then the largest term in the efficiency formula will be n or log n. If our algorithm is inefficient, then our formula will have a larger term like n^{2} and 2^{n}.