Contoh algoritme dan bukti yang tampaknya benar, tetapi tidak

Dalam kursus pengantar saya untuk pemrograman, kita belajar tentang metode Inisialisasi-Pemeliharaan-Pemutusan untuk membuktikan suatu algoritma melakukan apa yang kita harapkan. Tapi kami hanya perlu membuktikan bahwa suatu algoritma yang sudah diketahui benar, benar. Kami tidak pernah diminta untuk menunjukkan bahwa suatu algoritma tidak benar.

Apakah ada contoh algoritma klasik yang terlihat benar, tetapi tidak? Saya mencari kasus-kasus di mana pendekatan Inisialisasi-Pemeliharaan-Pengakhiran menangkap sesuatu yang intuisi pandangan pertama tidak.

Maksimum lokal 2D

$n \times n$$A$

$(i,j)$$A[i,j]$

$A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$$A$

maka setiap sel yang dicetak tebal adalah maksimum lokal. Setiap array yang tidak kosong memiliki setidaknya satu maksimum lokal.

$O(n^2)$

$A$$X$$X$$A$$(i, j)$$X$$(i, j)$$(i', j')$

$A \setminus X$$A$$X$$(i', j')$$A'$

$A'$$A$

$(i', j')$$A'$$A'$$(i', j')$$\diamond$

$\frac{n}{2}\times\frac{n}{2}$$A'$$(i, j)$

$T(n)$$n\times n$$T(n) = T(n/2) + O(n)$$T(n) = O(n)$

Dengan demikian, kami telah membuktikan teorema berikut:

$O(n)$$n\times n$

Atau sudahkah kita?