CS 6363.001: Design and Analysis of Algorithms - Spring 2022 Homework #1- Due: Feb. 3 Professor D. T. Huynh Problem #1. Do Problem# 2-4 (Inversions), p. 41 [Text]. Problem #2. Compare the following pairs of functions f(n),g(n) in terms of order of magnitude. In each case determine whether f(n) = O(g(n)), f(n) = O(g(n)), and/or f(n) = 8(g(n)): (Give a brief justification for your answers.) 1. f(n) = O.ln1.oos + loglogn, g(n) = 100n + (logn)52. f(n) = (loglogn)10glogn, g(n) = nl.5/logn3.f (n) = n6 2n+4, g(n) = 4n Problem #3. 1. Show that en = o( (log log log n r) for any constant C 2. Show that �i=l ik is 8(nk+1).Problem #4. Do Problem# 7.4-2, p. 184 [Text]. Problem #5 Do Problem# 4.3-8, p. 87 [Text] (Replace n2 in recurrence by n.) Problem #6 Do Problem # 4.3-9, p. 88 [Text] Problem #7. Solve the following recurrences using the method of iteration: (You may use asymtotic notations.) 1. T(n) = T(n - 3) + n, where T(O) = 12. T(n) = 6T(n/4) + n2, where n = 4k and T(l) = 1Problem #8. Do Problem# 4.4-9, p. 93 [Text] Problem #9. Do Problem# 6.5-9, p.166