Average case analysis

• Remember that we were interested in the expected running time: