<p><strong>2D local maximum</strong></p>

<p><strong>input:</strong> 2-dimensional $n \times n$ array $A$</p>

<p><strong>output:</strong> a local maximum -- a pair $(i,j)$ such that  $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value.  </p>

<p>(The neighboring cells are those among $A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$ that are present in the array.)  So, for example, if $A$ is</p>

<p>$$\begin{array}{cccc}
0&amp;1&amp;3&amp;\mathbf{4}\\
\mathbf{3}&amp;2&amp;\mathbf{3}&amp;1\\
2&amp;\mathbf{5}&amp;0&amp;1\\
\mathbf{4}&amp;0&amp;1&amp;\mathbf{3}\end{array}$$</p>

<p>then each bolded cell is a local maximum.  Every non-empty array has at least one local maximum.  </p>

<p><strong>Algorithm.</strong> There is an $O(n^2)$-time algorithm: just check each cell.  Here's an idea for a faster, recursive algorithm.</p>

<p>Given $A$, define cross $X$ to consist of the cells in the middle column, and the cells in the middle row.  First check each cell in $X$ to see if the cell is a local maximum in $A$.  If so, return such a cell.  Otherwise, let $(i, j)$ be a cell in $X$ with maximum value.  Since $(i, j)$ is not a local maximum, it must have a neighboring cell $(i', j')$ with larger value.</p>

<p>Partition $A \setminus X$ (the array $A$, minus the cells in $X$) into four quadrants -- the upper left, upper right, lower left, and lower right quadrants -- in the natural way.  The neighboring cell $(i', j')$ with larger value must be in one of those quadrants.  Call that quadrant $A'$.  </p>

<p><strong>Lemma.</strong> <em>Quadrant $A'$ contains a local maximum of $A$.</em></p>

<p><em>Proof.</em>  Consider starting at the cell $(i', j')$.  If it is not a local maximum, move to a neighbor with a larger value.  This can be repeated until arriving at a cell that is a local maximum.  That final cell has to be in $A'$, because $A'$ is bounded on all sides by cells whose values are smaller than the value of cell $(i', j')$.  This proves the lemma. $\diamond$</p>

<p>The algorithm calls itself recursively on the $\frac{n}{2}\times\frac{n}{2}$ sub-array $A'$ to find a local maximum $(i, j)$ there, then returns that cell.</p>

<p>The running time $T(n)$ for an $n\times n$ matrix satisfies $T(n) = T(n/2) + O(n)$, so $T(n) = O(n)$.  </p>

<p>Thus, we have proven the following theorem:</p>

<p><strong>Theorem.</strong> <em>There is an $O(n)$-time algorithm for finding a local-maximum in an $n\times n$ array.</em></p>

<p>Or have we?</p>

CC BY-SA 3.0
2018-03-31T08:08:58.610Z
At first reading, the only mistake I spotted was the recurrence solution. Is that the only mistake?
Radu GRIGore
CC BY-SA 3.0
2018-03-31T11:08:26.170Z
The recurrence is correct.  The algorithm is not!
Neal Young
CC BY-SA 3.0
2018-03-31T11:19:40.640Z
Ah, yes, I made a dumb mistake with the recurrence. I see the problem: the maximum you prove exists is not (necessarily) what you find. And what you find ignores the X.
Radu GRIGore
CC BY-SA 3.0
2018-03-31T11:42:56.517Z
Here's an example: $$\begin{pmatrix}2&1&4&3&3&0&0\\1&0&1&2&3&0&0\\0&{\color{red}1}&0&2&3&0&0\\2&2&2&2&2&2&2\\3&3&3&2&3&3&3\\0&0&3&2&3&0&0\\0&0&3&2&3&0&0\end{pmatrix}$$
Radu GRIGore
CC BY-SA 3.0
2018-03-31T15:48:34.720Z
(grr: the number in the center should be <2. Anyway, I'll stop spamming now.)
Radu GRIGore
CC BY-SA 3.0
2018-04-04T00:35:58.670Z
Thanks for this great example! Also, thanks @RaduGRIGore for helping with the wording: that proving the desired result is possible sometimes looks like, but is not necessarily, proving that that is what the algorithm finds
Marin
CC BY-SA 3.0
2018-04-04T05:11:24.817Z
@Marin, what is missing is a proof that a local maximum of $A'$ is also a local maximum of $A$, because it's not true. (I somehow like my initial wording, but it is not precise, and it is not clear. But, it may aid intuition.)
Radu GRIGore
CC BY-SA 3.0
2018-03-31T01:57:35.610Z
2018-03-31T01:57:35.610Z
Neal Young
<p>In my intro to programming course, we're learning about the Initialization-Maintenance-Termination method of proving an algorithm does what we expect it to. But we've only had to prove that an algorithm already known to be correct, is correct. We've never been asked to show that an algorithm isn't correct.</p>

<p>Are there any classic examples of algorithms that look correct, but aren't? I am looking for cases where the Initialization-Maintenance-Termination approach catches something that first-glance intuition doesn't.</p>

CC BY-SA 3.0
2018-03-29T19:53:46.277Z
Possibly of interest: https://cs.stackexchange.com/q/29475/755
D.W.
CC BY-SA 3.0
2018-03-31T02:14:47.050Z
Upvoting because I think that this is a very important pedagogical question.  It is slightly out of scope for cstheory, but I don't know a better platform for it, and there are many algorithms instructors in the cstheory community.   Most algorithm-design courses expose students only to correct, existing algorithms and to problems that are easily solvable using known techniques.  This reinforces the impression, so attractive to students, that one can safely trust one's intuitive feeling that a seemingly plausible algorithm is right.  A good algorithm-design course should do the opposite!
Neal Young
CC BY-SA 3.0
2018-03-31T11:28:01.803Z
I would love to have a collection like this.
Chandra Chekuri
<ds.algorithms><proofs>
Examples of algorithms and proofs that seem correct, but aren't
Marin
# Examples of algorithms and proofs that seem correct, but aren't

(Asked by: username_0 on 2018-03-29)

In my intro to programming course, we're learning about the Initialization-Maintenance-Termination method of proving an algorithm does what we expect it to. But we've only had to prove that an algorithm already known to be correct, is correct. We've never been asked to show that an algorithm isn't correct.

Are there any classic examples of algorithms that look correct, but aren't? I am looking for cases where the Initialization-Maintenance-Termination approach catches something that first-glance intuition doesn't.

**Tags:** ds.algorithms, proofs

> **Comments:**
> **username_1**: Possibly of interest: https://cs.stackexchange.com/q/29475/755  
> **username_2**: Upvoting because I think that this is a very important pedagogical question.  It is slightly out of scope for cstheory, but I don't know a better platform for it, and there are many algorithms instructors in the cstheory community.   Most algorithm-design courses expose students only to correct, existing algorithms and to problems that are easily solvable using known techniques.  This reinforces the impression, so attractive to students, that one can safely trust one's intuitive feeling that a seemingly plausible algorithm is right.  A good algorithm-design course should do the opposite!  
> **username_3**: I would love to have a collection like this.  

---

## 1 answers

### Answer by username_2 on 2018-03-31. Score: 20 | Accepted answer

**2D local maximum**

**input:** 2-dimensional $n \times n$ array $A$

**output:** a local maximum -- a pair $(i,j)$ such that $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value.

(The neighboring cells are those among $A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$ that are present in the array.) So, for example, if $A$ is

$$\begin{array}{cccc}
0&1&3&\mathbf{4}\\
\mathbf{3}&2&\mathbf{3}&1\\
2&\mathbf{5}&0&1\\
\mathbf{4}&0&1&\mathbf{3}\end{array}$$

then each bolded cell is a local maximum. Every non-empty array has at least one local maximum.

**Algorithm.** There is an $O(n^2)$-time algorithm: just check each cell. Here's an idea for a faster, recursive algorithm.

Given $A$, define cross $X$ to consist of the cells in the middle column, and the cells in the middle row. First check each cell in $X$ to see if the cell is a local maximum in $A$. If so, return such a cell. Otherwise, let $(i, j)$ be a cell in $X$ with maximum value. Since $(i, j)$ is not a local maximum, it must have a neighboring cell $(i', j')$ with larger value.

Partition $A \setminus X$ (the array $A$, minus the cells in $X$) into four quadrants -- the upper left, upper right, lower left, and lower right quadrants -- in the natural way. The neighboring cell $(i', j')$ with larger value must be in one of those quadrants. Call that quadrant $A'$.

**Lemma.** *Quadrant $A'$ contains a local maximum of $A$.*

*Proof.* Consider starting at the cell $(i', j')$. If it is not a local maximum, move to a neighbor with a larger value. This can be repeated until arriving at a cell that is a local maximum. That final cell has to be in $A'$, because $A'$ is bounded on all sides by cells whose values are smaller than the value of cell $(i', j')$. This proves the lemma. $\diamond$

The algorithm calls itself recursively on the $\frac{n}{2}\times\frac{n}{2}$ sub-array $A'$ to find a local maximum $(i, j)$ there, then returns that cell.

The running time $T(n)$ for an $n\times n$ matrix satisfies $T(n) = T(n/2) + O(n)$, so $T(n) = O(n)$.

Thus, we have proven the following theorem:

**Theorem.** *There is an $O(n)$-time algorithm for finding a local-maximum in an $n\times n$ array.*

Or have we?

> **Comments:**
> **username_4**: At first reading, the only mistake I spotted was the recurrence solution. Is that the only mistake?  
> **username_2**: The recurrence is correct.  The algorithm is not!  
> **username_4**: Ah, yes, I made a dumb mistake with the recurrence. I see the problem: the maximum you prove exists is not (necessarily) what you find. And what you find ignores the X.  
> **username_4**: Here's an example: $$\begin{pmatrix}2&1&4&3&3&0&0\\1&0&1&2&3&0&0\\0&{\color{red}1}&0&2&3&0&0\\2&2&2&2&2&2&2\\3&3&3&2&3&3&3\\0&0&3&2&3&0&0\\0&0&3&2&3&0&0\end{pmatrix}$$  
> **username_4**: (grr: the number in the center should be <2. Anyway, I'll stop spamming now.)  
> **username_0**: Thanks for this great example! Also, thanks @RaduGRIGore for helping with the wording: that proving the desired result is possible sometimes looks like, but is not necessarily, proving that that is what the algorithm finds  
> **username_4**: @username_0, what is missing is a proof that a local maximum of $A'$ is also a local maximum of $A$, because it's not true. (I somehow like my initial wording, but it is not precise, and it is not clear. But, it may aid intuition.)  

---

