Wiederholungsrelation für Zeitkomplexität

ich suche eine $\Theta$ Annäherung von

$$T(n) = T(n-1) + cn^{2}$$

Das habe ich bisher:

$$\begin{align*} T(n-1)& = T(n-2) + c(n-1)^2\\ T(n) &= T(n-2) + c(n-1) + cn^2\\[1ex] T(n-2) &= T(n-3) + c(n-2)^2\\ T(n) & = T(n-3) + c(n-2)^2 + c(n-1)^2 + cn^2 \\[1ex] T(n-3) &= T(n-4) + c(n-3)^2 \\ T(n) &= T(n-4) + c(n-3)^2 + c(n-2)^2 + c(n-1)^2 + cn^2 \end{align*}$$

An diesem Punkt wollte ich also verallgemeinern und ersetzen $k$ in die Gleichung.

$$T(n)= T(n-k) + (n-(k-1))^2 + c(k-1)^2$$

Jetzt fange ich an, den Basisfall 1 ins Bild zu bringen. Bei einigen früheren, einfacheren Problemen konnte ich meine verallgemeinerte k-Gleichung auf 1 setzen und dann nach lösen$k$. Dann setzen$k$ zurück in die Gleichung, um meine endgültige Antwort zu erhalten.

Aber ich stecke total auf dem $(n-k+1)^2$Teil. Ich meine, sollte ich das alles eigentlich vereiteln? Ich habe es getan und bekommen$k^2-2kn-2k+n^2 +2n +1 = 1$. An diesem Punkt denke ich, dass ich etwas falsch gemacht haben muss, da ich dies in früheren Problemen nie gesehen habe.

Könnte mir jemand Hilfe bei der Lösung dieses Problems anbieten? Ich würde es sehr begrüßen. Ich habe auch einen anderen Ansatz ausprobiert, bei dem ich versucht habe festzulegen$n-k = 0$ aus dem letzten Teil der Gleichung und bekam das $k = n$. Ich steckte n gegen Ende wieder in die Gleichung ein und bekam schließlich$n^2$als Antwort. Ich habe keine Ahnung, ob das richtig ist oder nicht.

Ich bin in einer Klasse zur Analyse von Algorithmen und wir haben angefangen, Wiederholungsrelationen durchzuführen. Ich bin mir nicht 100% sicher, ob ich dieses Problem richtig mache. Ich komme zu einem Punkt, an dem ich einfach festsitze und nicht weiß, was ich tun soll. Vielleicht mache ich das falsch, wer weiß. Die Frage kümmert sich nicht um Ober- oder Untergrenzen, sie will nur ein Theta.

Setzen Sie Ihre Überlegungen einfach wie folgt fort.

$$\begin{eqnarray} T(n) &=& T(n-1) + cn^2 \\ &=& T(n-2) + c(n-1)^2 + cn^2 \\ &=& \ldots \\ &=& T(n-n) + c(1^2) + c(2^2) + \ldots cn^2 \\ &=& T(0) +c\sum_{1\leq i\leq n} i^2. \end{eqnarray}$$

Wissen Sie, wie Sie dies mit der Additionsformel für die erste vereinfachen können? $n$ Quadrate?

Im Allgemeinen jede Wiederholungsbeziehung der Form $T(n) = T(n-1) + f(n)$ hat die Lösung $T(n) = \sum_{i=0}^n f(i)$.

Manchmal sind Formeln schwer zu merken, Integration kann praktisch sein -

$$\sum_{i=1}^n i^2 \approx \int_1^n i^2 di = \frac{1}{3}i^3 \bigg]_1^n = \frac{1}{3}(n^3 - 1) \leq cn^3 = O(n^3)$$