Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all local minima in the array?
Scan the entire array to check each cell to see whether it is a local minimum.
There's no algorithm that is asymptotically better; this is optimal to within a constant factor. (Proof: if there is any 3x3 region that you haven't looked at, it might contain a local minimum. So any correct algorithm will need to examine at least one cell out of each 3x3 region, i.e., must examine at least 1/9th of the array.)