previous | start | next

## Analyzing the Performance of the Selection Sort Algorithm

- The formula for the number of visits in the selection sort algorithm is (1/2) n2 + (5/2) n - 3.
- For large values of n, the latter terms in the formula have no significant contribution, so we just ignore them.

  > n | (1/2) n2 | (5/2) n - 3
  > 1000 | 500,000 | 2,497
  > 2000 | 2,000,000 | 4,997

- When comparing the ratios of counts for different values of n, the coefficient (1/2) cancels out.
- We simply say "The number of visits is of order n2" and use big-Oh notation: The number of visits is O(n2).
- For selection sort, doubling the number of elements increases the time needed for sorting fourfold.
- If a 1000 element vector takes 11 seconds, a 100,000 element vector will require over 3 hours!

previous | start | next