Recall that lasso is a linear model with a $l_1$ regularization.

Finding the parameters can be formulated as a unconstrained optimization problem, where the parameters are given by

> $argmin_\beta ||y - X\beta||^2 + \alpha||w||_1$.

In the constrained formuation the parameters are given by

> $argmin_\beta ||y - X\beta||^2 s.t.||w||_1 < \alpha$

Which is a quadratic programming problem and thus polynomial.

Almost all convex optimization routines, even for flexible nonlinear things like neural networks, rely on computing the derivative of your target w.r.t. parameters. You cannot take the derivative of $\alpha||w||_1$ though. As such you rely on different techniques. There are many methods for finding the parameters. Here's a review paper on the subject, [Least Squares Optimization with L1-Norm Regularization][1]. Time-complexity of iterative convex optimization is kind of tricky to analyze, as it depends on a convergence criterion. Generally, iterative problems converge in fewer epochs as the observations increase.


  [1]: http://www.di.ens.fr/~mschmidt/Software/lasso.pdf