You are given an n n matrix A with unknown values and your goal is to find an entry that is a local maximum with the smallest number of queries to individual entries. An entry Ai;j is a local maximum if it is not smaller than any of its neighbors (top, bottom, left or right if they exist) i. e. A(i, j) = max{ A(i, j), A(i-1,j), A(i, j-1), A(i+1,j), A(i, j+1)}. You only need to find a local maximum, not the global maximum. Note that there may be multiple local maxima.
1. Design an algorithm to find a local maximum in O(n) number of queries. (Hint: Start by thinking about a strategy for the 1D array first, and then extend it to the 2D setting.)
2. Prove the correctness of your algorithm.
3. Analyze the time complexity of your algorithm by finding a recurrence for the number of queries and solving it.