ผมก็ไม่แม่นเรื่องนี้ เพราะไม่ได้ใช้จริงจัง และเคยแต่อ่านผ่านๆ
สมมติว่าเราจะทำ Gaussian elimination ของ matrix ขนาด $n \times n$ แถวที่ $m$ แบบง่ายๆ
ขั้นแรก เราต้องการให้ $a_{m,m} = 1$ จึงต้องคูณสมาชิกทุกตัวของแถวที่ $m$ ด้วยค่า $\frac{1}{a_{m,m}}$ นับจำนวนครั้งที่คูณได้ $n - m + 1$ ครั้ง
ขั้นที่สอง เราต้องการให้ $a_{x,m} = 0$ สำหรับทุก $x > m$ ตรงจุดนี้ต้องคูณสมาชิกทุกตัวของแถวที่ $m$ ด้วยค่า $-a_{x,m}$ แล้วนำไปรวมกับสมาชิกแต่ละตัวของแถว $x$ นับจำนวนครั้งที่คูณและนำมาบวกได้ $2(n - m + 1)(n - m)$ ครั้ง
เราต้องทำสองขั้นตอนดังกล่าว ตั้งแต่ค่า $m = 1$ จนถึงค่า $m = n$ ดังนั้นจำนวน operation ที่ใช้คือ
\[\sum_{m = 1}^{n} (n - m + 1) + 2(n - m + 1)(n - m) = \frac{2n^3}{3} + \frac{n^2}{2} - \frac{n}{6}\]
จึงได้ complexity เป็น $O(n^3)$
ถ้าเข้าใจหลักการแล้ว น่าจะคำนวณกรณีที่ไม่ใช่ square matrix ได้นะครับ
