QS Avg: Formulation

• A(0) = 0

• If the pivot appears at position i, 1?i?n then A(i-1) comparisons are done on the left hand list and A(n-i) are done on the right hand list.

• n-1 comparisons are needed to split the list

Previous slide

Next slide

Back to first slide

View graphic version