Partition around a random pivot, then recurse into only the side containing rank k
| Scenario | Time | Why |
|---|---|---|
| Best / Average (random pivot) | O(n) | One-side recursion: n + n/2 + n/4 + ... = 2n |
| Worst (naive pivot) | O(n²) | Bad pivot shaves one element per step |
| Worst (median-of-medians) | O(n) | T(n)=T(n/5)+T(7n/10)+O(n) |
| Space (iterative) | O(1) | In-place partition, loop instead of recursion |
| vs full sort | O(n log n) | Selection asks for less → does less |
| vs heap top-k | O(n log k) | Heap streams; Quickselect needs all data |