What's the computational complexity of A\b in MATLAB? (A is a sparse non-square matrix)

MATLAB document says that if A is sparse and not a square, \ operation will turn to QR solver. I'm not very familiar with QR factorization either. Can anybody give an approximation of the complexity?

Thanks,

Junwei

[Walter Roberson]

http://epubs.siam.org/doi/abs/10.1137/0909057

However, that theory might not match the implementation.

[John BG]

It's time.

Computation complexity is the time it takes to solve it, that is usually equivalent to the amount of required computations, provided the time per operation is constant and known.

As explained in the link supplied by Walter, one can find bounds to the amount of operations

.. O(n^{{3 / 2}} )$ arithmetic operations, and the number of nonzeros in the Cholesky factor is $O(n\log n)$.

.. complexity bounds can be attained when A is nonsymmetric and indefinite, and either Gaussian elimination with partial pivoting or orthogonal factorization is applied.

.. Numerical experiments for a sequence of irregular mesh problems are provided.

So, consider tic tocing the operations of the experiments you perform, and then correlating the results to the amount of nonzeros, amount of operations, and then you will have measured the computational complexity of QR factorisation.