Quickselect

Mental model

Quicksort recurses into both halves; quickselect knows which half holds the answer and discards the other, so the work is n + n/2 + n/4 … which sums to O(n) rather than O(n log n). The catch is that the guarantee is only expected: adversarial or already-sorted input with a naive pivot degrades to O(n²), which is what randomised pivots and median-of-medians exist to prevent.

How to study Quickselect

Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use the linked roadmap and primary implementation references to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.

Next, compare Quickselect with Heap / Priority Queue, Complexity Analysis. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete k-th smallest by quickselect and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.

Proof of understanding

• Explain the mechanism from first principles and identify the state it reads or changes.
• Give one situation where the concept is the right choice and one where it is not.
• Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
• Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.

Where it matters

Median and percentile computation, top-k without full ordering, and the selection step inside median-of-medians.

Common mistakes

• Quoting O(n) as worst case — it is expected; the worst case is quadratic without a good pivot rule
• Reaching for a full sort when only one order statistic is needed
• Off-by-one between the k-th smallest and index k after partitioning
• Using a size-k heap for large k, where quickselect is cheaper, or quickselect for streaming data, where it does not apply

Learn from primary sources

Use the linked roadmap context and practice prompt.

Practice and explain it back

Review prompts

• Quickselect is O(n) and quicksort is O(n log n) despite the same partition step. Where does the log factor go, and why is the O(n) only expected?

Build evidence

Use a roadmap capstone to turn this concept into working evidence.

Learning paths

• DSA Practice