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.