Use the definition of "big Oh" to prove that is O(n). 2. (3 marks) Let f(n) and g(n) be positive functions such that f(n) is O(g(n)). Use the definition of "big Oh" to prove that f(n) g(n) is O(g (n)), where g (n) = g(n) g(n). 3. (3 marks) Use the definition of "big Oh" to prove that n +n is not O(n). 4. (6 marks) Consider the following algorithm for the search problem. Algorithm search (L, n, x) Input: Array L storing n 1 integer values and value x > 0. Out: Position of x in L, if x is in L, or -1 if x is not in L i 0 while (i