Introduction to the Design and Analysis of Algorithms
Textbook
 CS 3343/3341
 Analysis of Algorithms
 Fall 2012
 Recitation 9
 Answers to  
 In-Class Problems
    Week 9: Oct 23-25

You must follow the Rules for In-Class Recitations. Problem 1 is mainly present to give you a sample program that calculates the sum of a series. Of course the two series in Problem 2 differ is several ways from the series in Problem 1.

  1. Use the Master Theorem to analyze the following recurrences. (The theorem may not work for some of them.)

    [Application of the Master Method to the recurrences is carried out in the table below. Note that the case "Master fails" means that the Master Method does not apply in that case, as explained in the bottom of page 95 and on to 96. Exercise 4.6-2 (page 106) gives a solution in this case, but the material is too technical to come up often.]

    Recurrences, solution by Master Method, Examples
    Recurrenceab logb(a)nlogb(a) f(n)CaseBehavior
    T(n) = 3 T(n / 2) + n2 3 2log2(3) = 1.585 n1.585n2 3 Θ(n2)
    T(n) = 2 T(n / 2) + n2 2 2log2(2) = 1 n1n2 3 Θ(n2)
    T(n) = 64 T(n / 4) + √n 64 4log4(64) = 3 n3n0.5 1 Θ(n3)
    T(n) = 9 T(n / 3) + n2 log(n) 9 3log3(9) = 2 n2n2 log(n) noneMaster fails
    T(n) = 32 T(n / 2) + n2 log(n) 32 2log2(32) = 5 n5n2 log(n) 1 Θ(n5)
    T(n) = 125 T(n / 5) + 1 1255log5(125) = 3 n3n0 = 1 1 Θ(n3)
    T(n) = 16 T(n / 4) + n4 16 4log4(16) = 2 n2n4 3 Θ(n4)
    T(n) = 2 T(n / 4) + √n 2 4log4(2) = 1/2 n1/2 = √n √n 2 Θ(√n log(n))
    T(n) = 2 T(n / 4) + √n log(n) 2 4log4(2) = 1/2 n1/2 = √n √n log(n) noneMaster fails

  2. Suppose we use divide and conquer strategy and ordinary multiplication of 2-by-2 matrices, which require 8 multiplications. The recurrence T(n) = 8 T(n / 2) + Θ(n2) applies in this situation. Use the Master Theorem to find the big-Θ performance of this recurrence. [In Master Theorem, a = 8, b = 2, so log2(8) = 3. Also n3 > n2, so this is Case 1 and T(n) = Θ(n3).]

  3. Suppose we use the same approach using 3-by-3 matrices: a divide and conquer strategy for this case, where one will divide a 9-by-9 matrix into nine 3-by-3 matrices, and so on for larger powers of 3. First examine the standard way to multiply two 3-by-3 matrices, and see that this takes 27 multiplications. Write a recurrence for this situation. Again use the Master Theorem to find the big-Θ for your new recurrence. [In multiplying 3-by-3's, each inner product takes 3 mults and 2 adds, and there are 9 inner products, so we have 27 mults. Only Θ(n2) adds. Thus the recurrence is T(n) = 27 T(n / 3) + Θ(n2), a = 27, b = 3, so log3(27) = 3. As before, this is case 1, so T(n) = Θ(n3).]

Revision date: 2012-10-06. (Please use ISO 8601, the International Standard.)