= { r (1/2) + 2.3-3 Use mathematical induction to show that when n is an exact power of 2, the solu- tion of the recurrence 2 if n = 2, T(n) 2T (n/2) +n if n = 2k, for k > 1 is T(n) = n lgn. 2.3-4 We can express insertion sort as a recursive procedure as follows. In order to sort A[1..n], we recursively sort A[1..n 1] and then insert A[n] into the sorted array A[1..n 1]. Write a recurrence for the running time of this recursive version of insertion sort