Questions:

  1. What is another way of writing the summation (n-1) + (n-2) + ... + 1?   [Answer]

  2. Using the formula from your previous answer, compute the number of comparisons the Insertion Sort requires in the worst case to sort the following groups of items.   [Answer]
    1. 50
    2. 129
    3. 2,457
    4. 19,843
    5. 109,503

  3. Why do you suspect that the number of comparisons required in question 3 grows so rapidly? Rewrite the formula for the number of comparisons to confirm your suspicion.   [Answer]