Given an array $$[$a$\_1,$ a$\_2,\backslash$dots$,$ a$\_$n$]$$$,$ a reversal is a pair $$($i$,$j$)$$ such that $i $<$ j$ but $a$\_$i $>$ a$\_$j$$.$ 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$.\backslash$begin$\{$enumerate$\}\backslash$item $(11$ points$)$ What is the expected number of reversals in a random array? More formally, consider a random permutation of $n$ distinct elements $a$\_1,\backslash$dots$,$ a$\_$n$: what is the expected number of reversals? Give your answer precisely, without asymptotic notation. Prove your answer. $\backslash$item $(11$ points$)$ Recall the insertion sort algorithm: $\backslash$begin$\{$verbatim$\}$ for i $=1$ to n j $=$ i while j $>0$ and A$[$j$-1]>$ A$[$j$]$ swap A$[$j$]$ and A$[$j$-1]$ j $=$ j $-1\backslash$end$\{$verbatim$\}$ Suppose that our array has $d$ reversals. Prove that the $($worst$-$case$)$ running time of insertion sort is $$\backslash$Theta$($n $+$ d$)$$$.\backslash$item $(11$ points$)$ What does this imply about the $\backslash$emph$\{$average$-$case$\}$ running time of insertion sort as a function only of $n$$?$ That is$,$ if we draw a permutation uniformly at random, what is the expected running time of insertion sort $($in asymptotic notation$)?$ Note that this is $\backslash$emph$\{$not$\}$ a randomized algorithm; this is a deterministic algorithm on a random input.