1. (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 = (g)). (a) f (n) = n and g(n) = n/ 3 n. (b) f (n) = 100n + lg n and g(n) = n + (lg n)2. (c) f (n) = 10n lg n and g(n) = n lg (10n). (d) f (n) = 10 lg n and g(n) = lg (n2). (e) f (n) = n2/ lg n and g(n) = n(lg n)2. (f) f (n) = n2n and g(n) = 3n. (g) f (n) = 2n 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) (max{f (n), g(n)}). You should explicitly provide n0 and c as in the definition. 3. (6 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 x1, x2, . . . , x5 of A[1 . . . n] s.t. the following holds? x1 x2 + x3 x4 + x5 = 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, Fk = Fk1 + Fk2 for k 3 (notice the slight difference from the definition on slides). Prove that Fk+2 = k i=1 Fi + 1 for k 1. (b) There are n switches controlling a single light. Each switch has an on and an off position. Whenever we change the position of a switch, the status of the light changes (e.g, if the light is on, it will get turned off). Suppose at the beginning, all switches are at off position and the light is also turned off. Prove that whenever the light is off, there is always an even number of switches which is at on position.