Complexity analysis
Sorting & Search Lower Bounds
Decision trees, adversaries, and the stories behind classic impossibility results.
Hybrid 5 weeks · hybrid Advanced
470 GEL
Informational price—final fees appear on your admissions letter.
Request information
We animate comparisons, build decision trees on paper, and discuss when hardware realities break textbook models.
- Decision tree cutouts
- Adversary argument scripts
- Hardware cache awareness primer
- Pair exercises on randomized quicksort
- Guest talk on stable sort trade-offs
- Annotated bibliography
- Capstone essay on a chosen bound
- Sketch decision trees for small universes
- Explain why comparison lower bounds apply
- Connect cache awareness to real sorts
Mikheil Svanidze
CS instructor with research seminar experience.
Is linear-time sorting included?
Yes, with explicit assumptions on key ranges.
Math background?
Comfort with logarithms and simple recurrences is required.
Limitations?
No external memory model proofs.
“Sorting & Search Lower Bounds readings were dense, but the adversary scripts made oral exams less scary.”
Tako · Graduate student 