Aloha :)
Beim Gauß-Algorithmus hast du eine Matrix vorgegeben:$$M=\begin{pmatrix}a_{11} & a_{12} & \dots & a_{1n} & e_1\\a_{21} & a_{22} & \dots & a_{2n} & e_2\\\vdots & \vdots & \ddots & \vdots & \vdots\\a_{n1} & a_{n2} & \dots & a_{nn} & e_n \end{pmatrix}$$
In seiner einfachsten Form bringt der Gauß-Algorithmus eine quadratische Matrix auf Diagonalform. Die dazu notwendigen Schritte sind:
1) Division der Zeile 1 durch \(a_{11}\). Falls \(a_{11}=0\), setze eine nachfolgende Zeile an Pos. 1
2) Subtraktion des \(a_{n1}\)-fachen der Zeile 1 von den Zeilen \(n=2,3,\dots,n\)
3) Division der Zeile 2 durch \(a_{22}\). Falls \(a_{22}=0\), setze eine nachfolgende Zeile an Pos. 2
4) Subtraktion des \(a_{n2}\)-fachen der Zeile 2 von den Zeilen \(n=3,4,\dots,n\)
5) \(\ldots\)
Die benötigten Rechenoperationen sind:
1) \(n+1\) Divisionen für Zeile 1 (auch das Sollergebnis \(e_1\) muss dividiert werden)
2) \(n+1\) Multiplikationen und \(n+1\) Subtraktionen
\(\quad\)für jede der \(n-1\) Zeilen \(2,3,4,\dots,n\)
3) \(n\) Divisionen für Zeile 2
4) \(n\) Multiplikationen und \(n\) Subtraktionen für jede der \(n-1\) Zeilen \(1,3,4,\dots,n\)
Führt man dies fort kommt man auf folgende Anzahl Rechenoperationen:
$$T(n)=\left[(n+1)+2(n+1)\cdot(n-1)\right]+\left[n+2n\cdot(n-1)\right]$$$$\phantom{T(n)}+\left[(n-1)+2(n-1)\cdot(n-1)\right]+\left[(n-2)+2(n-2)\cdot(n-1)\right]$$$$\phantom{T(n)}+\dots+\left[1+2\cdot(n-1)\right]$$$$\phantom{T(n)}\ge2(n+1)\cdot(n-1)+2n\cdot(n-1)+2(n-1)\cdot(n-1)$$$$\phantom{T(n)}+2(n-2)\cdot(n-1)+\dots+2\cdot(n-1)$$$$\phantom{T(n)}=2(n-1)\sum\limits_{k=1}^{n+1}k=2(n-1)\frac{(n+1)^2+(n+1)}{2}$$$$\phantom{T(n)}=n^3+2n^2-n-2\in O(n^3)$$
