Questions:

  1. What is significant about the largest term in an algorithm's efficiency formula?   [Answer]

  2. What is order notation?   [Answer]

  3. Rank the following list of efficiency formulas from most efficient to least efficient: n2, n, 2n, log n, n3, 10n. (Hint: if you are unsure of the order, test each formula with several large values of n.)   [Answer]

  4. For the following four efficiency formulas, calculate the number of operations performed for n = 100, n = 1,000, and n = 10,000.   [Answer]
    1. n2
    2. n2 - n + 5
    3. n2 + 4n - 12
    4. n2 - 3n - 7

  5. Notice that formulas for parts b, c, and d in question 5 include extra terms that are not squared. For each value of n, find the number of operations that these terms contribute the total. Note that some of these values may be negative.   [Answer]

  6. Using the answers from question 5, find the percentage of operations that the non-squared terms contribute for each value of n. Round your answers to two decimal places. In general, what conclusion can you make about the contribution of the non-squared terms to the total number of operations?   [Answer]

  7. Do the concepts of efficiency and order notation only apply to sorting algorithms?   [Answer]