Suppose that $n - 1$ items $A_1,A_2,...,A_{n-1}$ have already been arranged in the increasing order, and that another item $A_n$ is to be inserted to preserve the order. What is the expected number of comparisons necessary to insert $A_n$?
Source: Taiwan 2001 p6
Tags: combinatorics
Suppose that $n - 1$ items $A_1,A_2,...,A_{n-1}$ have already been arranged in the increasing order, and that another item $A_n$ is to be inserted to preserve the order. What is the expected number of comparisons necessary to insert $A_n$?