Data Structures and Algorithms. You must justify your answer. When describing an algorithm, analyze its running time and explain why the algorithm is correct.

2. In each of the pairs of the functions below, verify using the definition of big Oh, whether f(n) = O(g(n)), g(n) = O(f(n)) or both. (a) f(n) = 20n2 + 14n + 7 g(n) = 50n (b) f(n) = n2 g(n) = 21 3. Prove T(n) = 2" - 1 using the base case and inductive hypothesis. 4. We can extend our notion to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n, m), we donate by O(g(n, m)) the set of functions O(g(n,m)) = { f(n, m) : there exist positive constants c, no, and mo, such that 0 = no or m >= mo} Give corresponding definitions for 12(g(n, m)) and (g(n, m)) 5. Indicate, for each pair of expressions (A, B) in the table below, whether A is O, N, O, o, w of B. Assume that k 21, >0 and c>1 are constant. Your answer should be in the form of the table with "yes" or "no" written in each box. B a. lg'in n b. nk ch c. Vn d. 2n 2n/2 e. nesc clon f. Ig(n!) lg(n"). n sinn (The following questions require short answer or short proof. If your proof is longer than 2-4 sentences, it might be wrong) 6. Consider a divide and conquer algorithm where the running time T(n) satisfies T(n) = 5T(n=2) + n for n 2 1 and T(1) = 0. What is the running time of the algorithm