Order the following functions according to their order of growth from the lowest to the highest. If you think that two functions are of the same order (i.e f(n) theta(g(n))), put them in the same group. log(n!), n^1.1, log log n, log n. n log(n), n^2, squareroot n, (n + 1)!, 2^n, n!, 3^n, 2^n + 1. For each pair of functions in the table below, determine whether f(n) O(g(n)), f(n) Ohm(g(n)), or f(n) theta(g(n)). Complete the table following the examples in the first throe lines. Prove asymptotic notation by definition Using the basic definition of O, Ohm, and theta, show that 10n^2 + 2n + 1 O(n^2) n^2 - 9n + 5 Ohm(n) 3n + 5 squareroot n + 2 theta(n). Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures. (To prove, use definitions of asymptotic notations. To disprove, find a counter example.) f(n) O(g(n) implies that g(n) O(f(n) + g(n)). f(n) O(g(n) implies that g(n) Ohm(f(n) + g(n)). f(n) Ohm(g(n) implies that 2^f(n) Ohm(2^g(n))