I already know the Big O for partial pivoting is $O(n^3)$ and remain the same for complete pivoting. I also know the big theta complexity for partial pivoting is $2/3 n^3$

I would like to know the complexity of complete pivoting in big theta


1 Answer 1


It's complicated. It depends on what 'counts 1'.

From the $\frac23n^3$ number you are reporting, I presume you are counting either multiplications or FMAs as your basic operations, which is one of the possible way to count "flops", or floating point operations.

In this case, the pivoting requires zero floating point operations, so it costs zero. The cost of GECP is still $\frac23n^3$. It is a weakness of the flops model that it cannot tell the two apart.

In real life, though, GECP does cost more than GEPP: you need more comparisons and memory reads and writes for the swaps. How should one count these operations? For instance, how many processor cycles do they take? It's complicated: there's caching, pipelines, hyperthreading and all sort of low-level stuff. The actual runtime will depend on the actual data in the matrix. On most computers in real-life conditions, even running the same code twice does not take exactly the same time. To get an idea how tricky predicting CPU times is, check this SO question, for instance.

Many researchers in scientific computing would tell you that at some point the only solution is to forget about big-theta operation counts and just measure real-world wall clock time on a sample machine. Operation counts are just an approximated model that is useful but can predict reality only up to a certain precision. As a wise man said, all models are wrong.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.