Randomized Quicksort Expected Comparisons

Problem

Return the expected number of key comparisons performed by randomized quicksort on n distinct keys.

The exact expectation is 2 * (n + 1) * H_n - 4 * n, where H_n is the n-th harmonic number. Return 0.0 for n <= 1.

Hint

A pair is compared only if one of the two is chosen as a pivot before they separate.

case 1

in: [1]

expected: 0

case 2

in: [2]

expected: 1

case 3

in: [5]

expected: 7.399999999999999

case 4

in: [10]

expected: 24.43730158730159

case 5

in: [100]

expected: 647.8502585632034

Starter codePython

def quicksort_expected_comparisons(n):
    # Your code here
    pass

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