Suppose you are given a matrix (a 2-dimensional array) A[1..m][1..n] of numbers. An element A[i][ j] is called good if each of its neighbors A[i1][ j], A[i+1][ j], A[i][ j1], and A[i][ j + 1] are at most A[i][ j]. For simplicity, assume elements beyond the boundaries of A are equal to . In other words, A[0][] = A[n + 1][] = A[][0] = A[][n + 1] = .

(a) Suppose m = 1 so we only have the array A[1][1..n]. Design and analyze in psuedocode with a proof an algorithm to find a good element of A in O(log n) time.

(b) Now suppose m = n. Design and analyze (with psuedocode and proof) an algorithm to find a good element of A in O(n log n) time. Hint: Suppose you know the maximum element of a column A[][ j], but it is not itself good. What can you say about the maximum elements of neighboring columns?

(c) Extra credit: Design and analyze an algorithm to find a good element of A in O(n) time.