Note: There may be some 'practice' problems which will NOT be graded. But they are equally important for the learning as the other ones. You don't need to submit your answer to these problems; submitting them is also fine (they will not be included in the grading anyway). 1. (7 points) For each of the following two functions f(n) and g(n), indicate whether f = O(g), or f = (g) or both (in which case f = O(g)). (a) f(n) = vn and g(n) = n/ vn. (b) f(n) = 100n + Ign and g(n) = n + (1gn)2. (c) f(n) = 10nlgn and g(n) = nig (10n). (d) f(n) = 10lgn and g(n) = 1g (n2). (e) f(n) = n2/lgn and g(n) = n(lgn)2. (f) f(n) = n2" and g(n) = 3". (g) f(n) = 2" and g(n) = 2n+100 2. (5 points) Suppose that f(n) and g(n) are asymptotically positive functions. Let h(n) = f(n)+ g(n). Prove that h(n) E O(max{f(n), g(n)}). You should explicitly provide no and c as in the definition. 3. (10 points) Let A[1...n] be an array of positive integers which are distinct. Is there a linear- time algorithm which can find five different elements :1, 12, ..., 25 of A[1. . . n] s.t. the following holds? X1 * 12 + 13 * T4 + 25 = 32767 If your answer is yes, provide such an algorithm; otherwise, argue why it is impossible. 4. This is a 'practice' problem which will NOT be graded. 'Proof by induction' is a method to prove a claim, in which (1) you prove that the claim holds for the initial or most trivial case (the base case), and then (2) show that if it holds for a certain value, it also holds for the next value (the induction step), so that the claim holds for all values (typically natural numbers). Use proof by induction to show the following: (a) Let the Fibonacci sequence be defined by: F1 = 1, F2 = 1, F* = Fk-1 + Fk-2 for k 2 3 (notice the slight difference from the definition on slides). Prove that Fk+2 = >Fi + 1 for k > 1