Bitok & Plintus
Bitok Bitok
Hey Plintus, ever wonder how the worst‑case for quicksort stretches out when you pick a really bad pivot? I’ve been chasing an edge case that seems to trip up the usual O(n²) analysis…
Plintus Plintus
If you always pick the worst pivot—say the smallest or largest element—each partition splits into a 0‑sized side and an (n‑1)-sized side. Then the recurrence is T(n)=T(n‑1)+Θ(n), which telescopes to Θ(n²). That’s why randomized pivots or median‑of‑three are standard; they keep the expected split closer to n/2 and the average cost back to O(n log n). In short, a consistently bad pivot turns quicksort into a quadratic‑time nightmare.