For a system $\mathbf{x=Da}$, there exist a lot of algorithms to estimate sparse vector $\mathbf{a}$. I wish to know the big-O mathematical complexity of 1) orthogonal matching pursuit (OMP) both with fixed sparsity and error tolerance criteria.2) L1-magic (which is based on interior point methods) algorithms. 
Mathematical Complexity of Sparse Solvers
linear solver;complexity