flop count & complexity

A flop is a single floating-point operation — one add, subtract, multiply, or divide. Counting flops is the simplest way to estimate how much work an algorithm does and how that work scales as the matrix grows. It is the numerical analyst's first-pass cost model: not exact wall-clock time, but a clean leading-order estimate that tells you which algorithm will still be running when the other has finished.

The classic counts every practitioner memorizes: dense LU factorization (Gaussian elimination) costs about (2/3) n^3 flops; Cholesky, exploiting symmetry, costs half that, (1/3) n^3; QR via Householder costs about (4/3) n^3; and the SVD or a full eigendecomposition costs a small constant times n^3. Solving with a factorization you already have is only O(n^2). Matrix-matrix multiply is 2 n^3; matrix-vector multiply is 2 n^2.

The reason these counts matter is scaling. An O(n^3) algorithm whose input doubles does eight times the work; triple the size and it is twenty-seven times slower. So the difference between O(n^2) and O(n^3) is not academic — it decides whether n = 100000 is a coffee break or a non-starter. This is precisely why iterative methods, at O(nnz) per step, dominate at large scale where O(n^3) is unthinkable.

A crucial caveat: flop count is not runtime. On real hardware, performance is often limited by memory traffic, not arithmetic — moving data between cache and main memory can cost far more than the flops themselves. Two algorithms with identical flop counts can differ tenfold in speed depending on how cache-friendly their memory access is. This is exactly the gap that blocked BLAS and LAPACK were engineered to close.