Complexity of Smoothed $\ell_0$ algorithm
There appear to be two user-introduced parameters $K,L$ in the algorithm you point to. Apart from that, the main task appears to be the computation of a pseudoinverse, and matrix multiplication. Without any further knowledge of the structure of the $n\times n$ matrix $A$, it would appear that the running time is $O(KL g(n))$, where $g(n)$ is your best estimate for computing the inverse and doing the multiplication. 

Crudely, both of these can be bounded by $cn^3$, but there might be better answers based on your actual setting (if A is sparse, or if you use Strassen's matrix multiplication, and so on)