Average case analysis

• Goal: to find out the expected running time of an algorithm.

• Assumption: every element of the input sequence is chosen as the pivot with the same probability.