4.10 Computational Complexity of Pivoting

Obviously, complete pivoting and partial pivoting differ substantially with regard to the computational effort required to determine the next pivot element. Complete pivoting on a dense, asymmetric matrix is an O(n³) operation requiring

$$\frac{2}{3}{n}^{3}+\frac{1}{2}{n}^{2}+\frac{1}{6}n$$

floating point comparisons. Partial pivoting on the same matrix is an O(n²) operation re­quir­ing

$$\frac{{n}^{2}+n}{2}$$

floating point comparisons.