| Terminazione dell'algoritmo | |
L'algoritmo che risolve il problema di Manhattan termina in un numero finito di passi qualunque sia il dato iniziale (m,n).La dimostrazione formale di questo fatto intuitivo si basa sul principio di induzione.
La base dell'induzione è
1) per i casi base l'algoritmo termina in 1 passo;
la proposizione induttiva grosso modo si può raccontare così
| 2) per ogni caso ricorsivo (m,n), applicando la regola ricorsiva, ci si riconduce a due casi (m-1,n) e (m,n-1) "più vicini" ai casi base. |  |