1. Consider an N by N matrix of integer numbers. Each individual raw is increasing from left to right; each individual column is increasing from top to bottom. Write a recursive function public static boolean inMatrix(int0] matrix, int x) with worst-case running time of O(N) that takes two parameters, the matrix matrix and a number x and decides if this number is in the matrix. Prove that the algorithm your function implements is correct. Prove that its worst-case running time in O(N). Hint: start by considering the top-right element in the matrix. (6 points: 3 pts code + 1 pt correctness proof + 2 points O(N) proof) 2. Give an example of two positive monotonic functions, f(n) and g(n), such that f (n) > g(n) for every n > 0 and f (n) = 0(n). Prove from the definition of big-O (i.e., by specifying the constants c and n, from the big-0 definition) that your functions satisfy the above condition. 3 pts (2 pts example + 1 pt proof) 3. Consider the following recursive method: int myFunction(int a, int b) { if (a >= b) return 1; else return myFinction(a, b-1) + myFunction(a+1, b); (a) (2 points) What is the return value of myFunction(0, 3)? Draw a recursive call tree to illustrate the series of method calls. (b) (2 points) What would be the return value, in general, for input values a and b, if a