U dssens digoITUIIIIIMUTUIPIILOLIVII e. T(n) = 7T(n/2) +18 (65) (Strassens algorithmadditions) Note that the term starting with 18 is written this way to show the divide and conquer reasoning, but you should write it as T(n) = 7T(n/2) + 9n2 For Asymptotic Analysis, You Don't Need to Know any Sums, Really Exercise 6 (Solving Recurrence Relations) Below you will find several different recurrence relations. Each of them (except the first one which you studied in CS 2050) is a recurrence relation that describes the amount of work required by some algorithm we will be studying in the "divide and conquer chapter coming up. For all parts assume that the given recurrence applies for n >1 and that T(1) = 1. For each part, analyze assuming n = 2" ("B" in the preceding discussion is 2 for all these). When you finish doing the "substitute and extrapolate process to get an expression for T(n) involving a series, figure out how to add up the series to get an expression for T(n) You could do these by figuring out the values for a, b, c, and d in the preceding discussion and plugging them in to the final results, but that is actually more irritating, probably, than just doing the substitution, extrapolation, and summing up yourselves, and would be much less insightful. Then, in each part, figure out the efficiency category for Tn), in terms of n. Also, if you end up with a function that has a constant as the base and n mixed in to the exponent, use the logarithm property discussed earlier to write it with n as the base. Page 24 CS 4050 Spring 2020