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 in Matrix(int[][] matrix, int x) with worst-case running time of O(N) that takes two parameters, the matrix matrix and a number 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) = O(n). Prove from the definition of big-O (i.e., by specifying the constants c and no from the big-O definition) that your functions satisfy the above condition. 3 pts (2 pts example + 1 pt proof)