mathematical induction

1. Use mathematical induction to show that when n is a power of 2, T(n) = n lg n is the
   solution of the recurrence relation
   T(n) = (
   2 if n = 2
   2 · T(
   n
   2
   ) + n if n = 2k
   for k > 1.
2. Suppose we are comparing implementations of Insert-sort and Merge-sort on
   the same machine. For input of size n = 2k
   for k ≥ 1, Insert-sort runs in 8n
   2
   comparisons, while Merge-sort runs in 64n lg n comparisons. For which value of n
   does Insert-sort beat Merge-sort?
3. We can express Insert-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 sorted array A[1…n−
   1].
   (a) Write the pseudocode for this recursive version of Insert-sort, name it Insertsort-recur.
   (b) Write a recurrence for the running time of of Insert-sort-recur.
   (c) Find the solution of the recurrence relation in (b).
   (d) Is Insert-sort-recur more expensive than Insert-sort?
4. Given an array s = hs[1], s[2], . . . , s[n]i, and n = 2d
   for some d ≥ 1. We want to find
   the minimum and maximum values in s. We do this by comparing elements of s.
   (a) The “obvious” algorithm makes 2n − 2 comparisons. Explain.
   (b) Can we do it better? Specify a divide-and-conquer algorithm.
   (c) Let T(n) = the number of comparisons your divide-and-conquer algorithm makes.
   Write a recurrence relation for T(n).
   (d) Show that your recurrence relation has as its solution T(n) = 3
   2
   n − 2.
5. Let S be an array of n integers such that S[1] < S[2] < · · · < S[n]. (1) Specify
   an O(lg n) algorithm which either finds an i ∈ {1, 2, . . . n} such that S[i] = i or else
   determine that there is no such i. (2) Justify the correctness and running time of your
   algorithm.

Sample Solution