{\bf 1.  Average-case analysis of insertion sort} (9 + 9 + 2 = 20 points)

While the worst-case running time of both insertion sort and quicksort
is $\Theta(n^2)$, quicksort is considered an efficient sorting
algorithm, because its average-case running time is $\Theta(n \lg n)$.
In this exercise, we analyze the average-case performance of insertion
sort.

Let $A[1..n]$ be an array of distinct numbers.  If $i < j$ and $A[i]
> A[j]$, then we say that the pair $(i,j)$ is an {\em inversion}\/ of
> $A$.
\begin{enumerate}
\item[(a)] If $T(A)$ is the running time of insertion sort on input $A$ and
$I(A)$ is the number of inversions in $A$, then prove that $T(A)$ is
$\Theta(I(A) + n)$. 

\item[(b)]
Show that if $A$ is a random permutation chosen uniformly at random
from the set of all $n!$ permutations, then the expected number of
inversions is $\Theta(n^2)$.

\item[(c)]
Using parts~(a) and~(b), derive a tight bound on the expected running
time of insertion sort if the input is a random permutation.
\end{enumerate}
