Изменения

Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] <= R[i][j] <= R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать - <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] <= R[i+1][j+1] <= R[i+2][j+1] </tex>. Таким образом, заполняя одну диагональ, алгоритм сделает не более n шагов, а так как диагоналей n, получили асимптотику <tex> O(n^2) </tex>.