$2\mathrm{.}3-3$

Use mathematical induction to show that when $n$ is an exact power of $2,$ the solu$-$

tion of the recurrence

$T(n)=\{\begin{array}{ccc}2& if& n=2\\ 2T(\frac{n}{2})+n& ifn=2^k,\text{f}\text{o}\text{r}& k>1\end{array}$

is $T(n)=nlgn.$

$2\mathrm{.}3-4$

We can express insertion sort as a recursive procedure as follows. In order to sort

$A[1$dotsn$],$ we recursively sort $A[1$dotsn$-1]$ and then insert $A[n]$ into the sorted array

$A[1$dotsn$-1].$ Write a recurrence for the running time of this recursive version of

insertion sort.