Given an array $[$a$1,$ a$2,...,$ an$],$ a reversal is a pair $($i$,$ j$)$ such that i $<$ j but ai $>$ aj $.$ For example,

in the array $[5,3,2,10]$ there are are three reversals $((1,2),(1,3),(2,3)).$ Note that the array has

no reversals if and only if it is sorted, so the number of reversals can be thought of as a measure of

how well$-$sorted an array is$.$

$($a$)(11$ points$)$ What is the expected number of reversals in a random array? More formally,

consider a uniformly random permutation of n distinct elements a$1,...,$ an: what is the

expected number of reversals? Give your answer precisely, without asymptotic notation.

Prove your answer.

$($b$)(11$ points$)$ Recall the insertion sort algorithm: