Exercise 3: "Quicksort Is Always Faster" — What's Missing — Possible Solution ==================================================================== WHAT'S MISSING FROM THE CLAIM ------------------------------ The teammate's claim treats quicksort's typical, average-case reputation as if it were a guarantee. Per this chapter's own honest caveat, quicksort's O(n log n) performance is specifically its AVERAGE case - Chapter 4's own best/worst/average-case distinction applies here exactly as it did to linear search and hash tables earlier in this course. Quicksort also has a genuine WORST case of O(n^2), the same complexity class as bubble sort, under specific input conditions. A CONCRETE SITUATION WHERE QUICKSORT DISAPPOINTS ------------------------------ Per this chapter's own finding, if quicksort's pivot selection is naive (for example, always choosing the first or last element as the pivot) and the input data happens to already be sorted (or reverse- sorted), every partition step produces a maximally unbalanced split - one side with nearly all the remaining elements, the other side with almost none. This is exactly the worst-case scenario, degrading performance to O(n^2) - potentially disastrous on a large, already- mostly-sorted dataset, which is a genuinely common real-world situation (e.g., re-sorting data that's already nearly in order after a small update). WHY THIS ISN'T JUST A THEORETICAL CONCERN ------------------------------ Per this chapter's own note, real implementations defend against this with randomized or median-of-three pivot selection specifically because naive pivot choices on structured (not random) real-world data can reliably trigger the worst case - this isn't a purely theoretical edge case invented for a textbook, it's a documented, practical failure mode serious enough that production sorting libraries are specifically engineered to avoid it. WHY THIS WORKS AS AN ANSWER ------------------------------ The explanation identifies the specific case (average vs. worst) the teammate's claim conflates, using this chapter's own explicit caveat and Chapter 4's own case-distinction framework, and gives a concrete, plausible real-world trigger (already-sorted input with naive pivot selection) rather than treating the worst case as a purely abstract possibility.