Laufzeit eines Algorithmus ermitteln

Question

$$ n + \sum _{j=\:i\:+1}^n\: (tj) + \sum _{j=\:i\:+1}^n\: (tj - 1) + (n - 1) $$

Wie muss ich hier mit den Summen umgehen und wie kann ich auf eine Laufzeit Θ(n²) kommen? Könnte mir hier vielleicht jemand helfen?

LG

Answer 1

Ist t eine Konstante?

Wenn ja: Schreibe t vor das erste Summenzeichen.

Die zweite Summe kannst du als Differenz von zwei Summen schreiben. Danach beim ersten Teil auch t vor das Summenzeichen nehmen.

Formel für "arithmetische Reihen" anwenden bei den Summen, die noch über j laufen.

Comments

Da t eine Konstante ist kann ich sie wegfallen lassen, wenn ich dann die Summenformel noch darauf anwende müsste es so aussehen

$$  n + \frac{n^2+n}{2} + \frac{n^2-1}{2} + (n - 1)  $$

Was mir sagt Ο(n²) also auch Θ(n²) ?

---

Was mir sagt Ο(n^{2}) also auch Θ(n^{2}) ?

Du meinst das Landau-Symbol:

https://de.wikipedia.org/wiki/Landau-Symbole#Definition

Was sagt mir Ο(n^{2}) also auch Θ(n^{2})?

Dass die Laufzeit ungefähr quadratisch oder genau nicht mehr als quadratisch wächst. n^{2.1} wäre z.B. schon ausgeschlossen. 

Vereinfache deinen Term noch. Addiere die Brüche usw. Dann kannst du den lim sup bestimmen für g(n) = n^2 und das gegebene f.