Next, we want to consider the "middle" element of A and try to infer about the four smaller subproblms. Let mR=21+n and mC=21+n, row and column indices respectively of the "middle row" and "middle column". Note: When you consider a (sub)problem where the indices of rows/column involved are different, then you will correspondingly compute values of mR and mC. Consider A[mR,mC], i.e., "usual" middle element when we consider rows 1 through n and columns 1 through n (in general, the value at the bottomright corner of the top-left quadrant of the part of the array in consideration). (b) (5 pts) Suppose A[mR,mC]x. What can you infer about each of the four subproblems A1,A2,A3, and A4 ? Clearly identify the ones that do not have to solved anymore, and those that still have to be solved. Briefly justify. (d) (15 pts) Use your observations from (b) nd (c) to present complete pseudocode for solving the problem of looking for x in A[ij,kl] using divide and conquer by specifying details of the following. Invoking the algorithm as search (A,1,n,1,n,x) solves the original problem. // Solves the problem of looking for x in A[ij,k. ) ) // Returns true if x is present in A[ij,k1]; I/ returns false otherwise 1/ Pre: (1) each of rows i through j is in nondecreasing order 1/ (left to right) I/ (2) each of columns k through 1 is in nondecreasing order 11 (top to bottom) boolean search (A,i,j,k,1,x) \{ \} You must clearly specify the base case(s). (5 pts) Model T(n), the complexity of your algorithm when invoked as search (A,1,n,1,n,x), via a recurrence. Find a theta bound for T(n). Feel free to use the Master Theorem, if it can be used