Quickselect Expected Remaining Size

Problem

Return the expected size of the remaining subarray after one random-pivot partition in quickselect.

A uniformly random pivot rank p leaves max(p - 1, n - p) elements on the larger side, so average that quantity over p from 1 to n. Return 0.0 for n <= 1.

Hint

The larger partition side shrinks geometrically by a constant factor in expectation.

Test cases

case 1

in: [1]

expected: 0

case 2

in: [2]

expected: 1

case 3

in: [5]

expected: 3.2

case 4

in: [10]

expected: 7

case 5

in: [0]

expected: 0

Starter codePython

def quickselect_expected_remaining(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor