Data la seguente ricorrenza:
T(n) = T(n-1) + n^2
Come posso dimostrare che è O (n ^ 3) con il metodo di sostituzione? L'ipotesi O (n ^ 3) deriva dal fatto che ad ogni passo della ricorsione paghiamo n^2 e abbiamo n passi di ricorsione avendo quindi: n * n^2 = n*3 .
Mi aspetterei che questo sia theta (n ^ 3), ma non posso nemmeno provare O (n ^ 3).
Ho provato con l'ipotesi:
T(n) <= n^3 + n^2 * c1 + n * c2 + c3
ma ciò produce:
T(n) <= n^3 + n^2 * (3 + c1) + n * (c2 - 2c1 -1) + (c1 - 1 - c2 + c3)
che produce:
-
c1 = c1 + c -
c2 = c2 - 2c1 - 1 -
c3 = c1 - 1 - c2 + c3
Ma anche dal primo ( c1 = c1 + c ) troviamo che nessun c1 , c2 o c3 soddisfano le equazioni.
Che cosa ho fatto di sbagliato?