Pivot element selection in Quick Select

Question

Is there any significance of selecting a random pivot over last element for quick select?

I can still find the required element by always selecting the last element as pivot. Will it effect the runtime.

Answer 1

The choice of pivot has a huge influence on the runtime of quickselect on a given array.

In deterministic quickselect, if you always choose the last element as your pivot, imagine what happens if you try to select out of an always-sorted list. Your pivot will always be the worst possible pivot and will only eliminate one number from the array, leading to an Θ(n²) runtime.

In randomized quickselect, it's still technically possible that the runtime will be Θ(n²) if the algorithm always makes the worst possible choice on each recursive call, but this is extraordinarily unlikely. The runtime will be O(n) with high probability, and there is no "killer" input.

In other words, quickselect with a deterministically-chosen pivot will always have at least one "killer" input that forces it to run in time Θ(n²), while quickselect with a random pivot has no killer inputs and has excellent average time guarantees. The analyses are totally different as a result.

Hope this helps!