Roadmap

• Quicksort and how it works

• Three different views on complexity:

  • worst case analysis
  • average case analysis
  • smoothed analysis