Lösung lineares Gleichungssystem (Komplexität)

Informatik schrieb:
> In einer Vorlesung wurde am Rande die O-Notation eingeführt. Zur
> Lösung von LGS eignet sich die QR-Zerlegung. Dabei wird schrittweise ein
> Element der zu zerlegenden Matrix zu null gesetzt. Demnach müsste die
> Matrix nach [math] \sum_{i =  1}^{n-1} (n - i) /math] Durchläufe in Form
> einer Dreiecksmatrix vorliegen.
> Ein Wikipedia-Eintrag hierzu
> https://de.wikipedia.org/wiki/Givens-Rotation schätzt den Aufwand zu
> O(n^2) ab (n*m Matrix-Matrix Produkte seien zu bilden).
> Ein weiterer Eintrag hierzu
> https://fsi.cs.fau.de/forum/thread/7466-Komplexita... schätzt den
> Aufwand zu O(n^3) ab.
> Meine Frage:
> Was stimmt an meiner Überlegung zur Anzahl an Durchläufen einer QR
> Zerlegung nicht, bzw. wie kommt man zur Angabe O(n^2), bzw. O(n^3)?

Pack das ganze doch mal in eine, für den Leser, lesbare Form...