First Sort I
Problem 523
Consider the following algorithm for sorting a list:
For example, the list { 4 1 3 2 } is sorted as follows:
Let F(L) be the number of times step 2a is executed to sort list L. For example, F({ 4 1 3 2 }) = 5.
Let E(n) be the expected value of F(P) over all permutations P of the integers {1, 2, ..., n}.
You are given E(4) = 3.25 and E(10) = 115.725.
You are given E(4) = 3.25 and E(10) = 115.725.
Find E(30). Give your answer rounded to two digits after the decimal point.