1. (10 points) Is 3n+10(3")? Is 33m-O(3")? Explain your answers. 2. (10 points) Assume > 0 to be a fixed positive real number. Show that log3 n-o(n'), where log3 n = (log n)3. (Hint: You may want to use L'Hospital's rule) 3. (60 points) Consider the following three functions of n n2 for even n n for odd n n2 for 1 120 fs(n) n2 for all n 1 Indicate for each pair of expressions (A. B) in the table below, whether A is 0,0.0,w, or of B Your answer should be in the form of a table with "yes" or "no" written in each box. Show your work. You need to show the relation between each pair of functions based on which you will fill up the table. (Each correct entry in the table is worth 1 point. There are 30 such entries. Correct relation for each pair of functions worth 5 points. There are 6 such pairs) 0 Cu fi(n)f2(n) fi(n)fs(n) f2(n f3(n) fs(n)fi(n) (n)2(n) 4. (20 points) let f(n) and g(n) asymptotically positive functions. State whether the following state- ments are TRUE or FALSE. In case a statement is TRUE, prove it using definitions of 0.. w o etc. In case it is FALSE, provide a counter example (a) f(n) - O(g(n)) implies g(n) -O(f(n)) (b) f(n) + g(n) = (min(f(n), g(n))) (c) f(n) - Q(f(n/2)) 5. (20 points) List the following functions in the order of decreasing growth rate by testing dominance. All logarithms are to the base 2. Use one or two lines of justification if required 2log n, no.9, log(n"), 4log logn, log log n, log n, n log2n, 4logn, nl/logn, nlogv2 You can use the following known properties of logarithm: log, a n log, a, log,a loga/logb, log, a 1/loga b, alocoa 6. (30 points) Big-Oh and Run Time Analysis: Describe the worst case running time of the following pseudocode functions in Big-Oh notation in terms of the variable n. Showing your work is not required (although showing work may allow some partial credit in the case your answer is wrong dont spend a lot of time showing your work. Some high level explanation is good enough) You MUST choose your answer from the following (not given in any particular order) O(n), O(n2),O(n3), O(n4), O(n log n) I. void silly (int n) ( - ni while (j > 0) { System.out.println("j -" j)i II. void silly(int n, int x, int y) f for (int k n; k > 0; k--) if(x <>