Lower Bound For Average II

• There are n(n-1)/2 inversions in a permutation and its reverse.

• Assuming that all n! permutations are equally likely, there are n(n-1)/4 inversions in a permutation, on the average.

• The average performance of a “swap-adjacent-pairs” sorting algorithm will be ?(n2).

Previous slide

Next slide

Back to first slide

View graphic version