Recurrences and Asymptotics

Let T(n) be the time complexity of an algorithm to solve a problem of size n. Assume T(n) is O(1) for any n less than 3. Solve the following recurrence relations for T(n). (a) [3 points] T(n) = 8T (6.) + n2 (b) [3 points] T(n) = 8T(Vn) + log+ n. (c) [5 points] T(n) = T(n 1) + 3n. (d) [5 points] T(n) = T(n/7) + 2T (n/5) + O(n). (e) [14 points] Consider the following functions. Within each group, sort the functions in asymptotically increasing order, showing strict orderings as nec- essary. For example, we may sort n, n, 2n as 2n = O(n) = o(n). 1. [4 points] log n, yn, log, n, log n", log log n20, log n. 2. [5 points] n?, n log na, na log log n, 3, log(n!). 3. [5 points] (log n), (log n)n-1,5", nlogn