For the average case of Insertion Sort we assumed that because a list can have at minimum

$0$ inversions and at maximum C$($n$,2)$ inversions then we can conclude that an average list

has C$($n$,2)/2$ inversions. This is a somewhat hasty conclusion with weak evidence. Let$$s

investigate this in more detail. In what follows assume a list of length n contains the values $1$

through n$.$

$($a$)$ Suppose a list A has exactly k inversions. If A$$ is the reversed version of A$,$ explain why $[10$ pts$]$

A$$ has exactly C$($n$,2)$ k inversions.

Solution:

$($b$)$ Looking at all possible lists of length n explain why the average number of inversions is $[15$ pts$]$

actually C$($n$,2)/2$