Question 3 (5 points). Finding the maximum element. You are given an array A of size n (n > 3). The first k elements (k > 2) are in strict increasing order, i.e., for 1 sisk, A[i] A[i]. k is unknown. In other words, A[k] is the maximum element in A. a. Give a nave algorithm that runs in O(n) time to find k. (1 point) FINDMAX-NAIVE(A, 1, n) // 1 is the starting index, and n is the ending index. 1. for k= to 2. if A[k]> and A[k]> 3. return k b. Give an algorithm of the same function that runs in (Ign) time. Write two pseudocode implementations: a recursive one and an iterative (i.e., non-recursive) one. Hint: Use the similar method that is used for binary search (from assignment 1), considering the relationship between A[k] with its neighbor elements. (3 points) Recursive implementation Iterative implementation FINDMAX-RECURSIVE(A, 1, n) 1. k= (1 + n)/2] 2. if A[k]> and A[k] > 3. return k 4. else if A[k] and A[k]> 5. return k 6. else if A[k]