CIS 320 Homework Assignment 2 [160 pts] Solutions

CIS 320 Homework Assignment 2 [160 pts] Solutions Please see Piazza and Canvas for submission logistics and LATEXtemplate. 1. For each of the following recurrences, give an expression for the runtime T(n) using the Master Theorem or state that it does not apply. (a) T(n) = T(n/2) + log n (b) T(n) = 2T(n/2) + log n (c) T(n) = nT(n/2) + 1 (d) T(n) = 1 2 T(n/2) + n (e) T(n) = 27T(n/3) + n 4 Solution: The Master theorem can help us analyze a recurrence of the form T(n) = a · T(n/b) + n c . (a) As presented in class, the Master theorem does not apply, since log n 6= n c for any c ∈ R. However, if you used the unsimplified version of the Master theorem presented in the textbook, you would also receive credit (the unsimplified Master theorem would still not apply here). (b) As presented in class, the Master theorem does not apply, since log n 6= n c for any c ∈ R. However, if you used the unsimplified version of the Master theorem presented in the textbook, you would also receive credit (you could apply it here to conclude T(n) = Θ(n)). (c) In this case, we have a = n, but a must be constant, so we cannot apply the Master theorem. (d) In this case, we have a = 1 2 , but we need a ≥ 1, so we cannot apply the Master theorem. (e) In this case, we have a = 27, b = 3, c = 4. Since we have logb a = log3 27 = 3 4 = c, then by the Master theorem, T(n) = Θ(n 4 )