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(n3) operation requiring

23n3+12n2+16n\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(n2) operation requiring

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

floating point comparisons.