title: Find local minimum in n x n matrix in O(n) time
body: <p>So, this is not my home work question, but it is taken from an ungraded homework of the coursera course on algorithms and data structures (which is now complete). </p>
  
  <p>You are given an n by n grid of distinct numbers. A number is a local minimum if it is smaller than all of its neighbors. (A neighbor of a number is one immediately above, below, to the left, or the right. Most numbers have four neighbors; numbers on the side have three; the four corners have two.) Use the divide-and-conquer algorithm design paradigm to compute a local minimum with only O(<em>n</em>) comparisons between pairs of numbers. (Note: since there are <em>n</em><sup>2</sup> numbers in the input, you cannot afford to look at all of them. Hint: Think about what types of recurrences would give you the desired upper bound.)</p>
  
  <p>Since the numbers are not in any order, I don't see how we can get away with any thing but O(<em>n</em><sup>2</sup>) comparisons.</p>