Average case analysis

• The interesting point is again the number of comparisons. Therefore we define:

• Thus the number of comparisons for a sequence of n elements is