1. (Problem 3.1-1) Let f(n) and g(n) asymptotically positive functions. Prove that f(n) + g(n) = (max(f(n), g(n)). 2. Prove or disprove: If f(n) = (g(n)), then f(n)2 = (g(n)). 3. Prove or disprove: If f(n) = @(g(n)), then 2f(n) = @(29(n)). n > 4. Let f(n) and g(n) be asymptotically positive functions, and assume that lim g(n) = 0. Prove that if f(n) = @(g(n)), then ln(f(n)) = o(ln(g(n))). 5. (Problem 3.2-8) Show that if f(n) In f(n) = O(n), then f(n) = O(n/Inn). Hint: use the result of the preceding problem. 6. Consider the statement: f(cn) = o(f(n)). a. Determine a function f(n) and a constant c > 0 for which the statement is false. b. Determine a function f(n) for which the statement is true for all c > 0. 7. Determine the asymptotic order of the expression 21=1 a' where a > 0 is a constant, i.e. find a simple function g(n) such that the expression is in the class (g(n)). (Hint: consider the cases a = 1, a > 1, and 0 1. 30