Lesson 5.1: Sort Complexity
Class Meeting:
| Section | Slides | Annotated Slides | Video |
| 12–1PM | 5.1-sortcomplexity-203-1221.pdf Download 5.1-sortcomplexity-203-1221.pdf | PDF Download PDF |
On Cloud Recordings in Canvas Zoom soon after lecture |
| 1–2PM | 5.1-sort-complexity-1pm.pdf Download 5.1-sort-complexity-1pm.pdf | 5.1-sort-complexity-1pm-annotated.pdf Download 5.1-sort-complexity-1pm-annotated.pdf |
On Canvas Zoom Cloud Recordings |
| 4–5PM | 5.1-sort-complexity-4pm.pdf Download 5.1-sort-complexity-4pm.pdf | 5.1-sort-complexity-4pm-annotated.pdf Download 5.1-sort-complexity-4pm-annotated.pdf |
On Cloud Recordings in Canvas Zoom |
Readings:
- Carrano & Henry : Chapter 2 (Recursion),
- Carrano & Henry : Chapter 11.2.1 (Merge sort)
- Epp : Chapter 5.6 - 5.7 (Recurrence relations)
Summary:
This lesson completes our study of recurrences. We use the solution of the running time recurrence for Merge Sort to illustrate recursion trees, and to argue a tight O(n log n) running time. In the second portion of the day, we prove a tight lower bound of $\Omega(n\log n)$ for ALL comparison-based sorting algorithms!
Learning Outcomes:
- Use a recurrence tree to derive a closed form for the running time of Merge Sort.
- Prove Merge Sort is Correct.
- Use a decision tree to argue the lower bound on all comparison based sorting algorithms.