Average case analysis

• In order to analyze this, let e be the first pivot element with ai ≤ e ≤ aj.

  • If ai < e < aj, then ai and aj are not compared.
  • Otherwise, either ai = e or aj = e holds. Then the two elements are compared. This case happens with probability