Homework Assignment #7

To learn how to solve recurrence relations for typical divide-and-conquer algorithms, including the use of the “change of variable” technique.

Show all work. i.e., justify your answers.

• Part III (Section 3.2): exercises 1 and 2 in the Recurrence Relations notes.

• Analyze the running time of 3-part Mergesort (like traditional mergesort but involves dividing the problem into thirds rather than into halves) using Recurrence Relations solution techniques. You may conclude with the general solution, since you have no initial conditions, or you can choose your own initial conditions. (Do not use the Master Theorem.)

• Exercise 2.4 in the text book (use the Master Theorem where possible)