Remember
- Best, average and worst case are separate statements. O(n^2) worst does not mean slow on every input.
- Insertion sort: n - 1 comparisons on sorted input, n(n-1)/2 on reversed, about n^2/4 on random.
- Ask which case a bound describes before comparing two algorithms by it.