CSSE 230: Session Notes - Day 26

Topics

1. Quicksort
2. Recurrence relations

Outline

1. [15 min] Quicksort
2. [5 min] Definition of recurrence relations
3. [30 min] Developing and solving a recurrence relations for
   • Worst case of linear search
   • Worst case of binary search
   • Worst case of merge sort
   • Best case of merge sort
   • Worst case of quick sort
   • Average case of quick sort (if time permits)
4. [5 min] Break
5. [balance of time] Work on pair project

Resources

• QuickSort code.
• Slides for recurrence relations
• Quicksort partition animation

Homework

1. Day 28, BC: Recurrence homework, Analysis 2 homework, and Analysis 3 homework