really quickly:

matrix inversion is ~O(n^3)

gradient descent is ~O(np) where p is the number of predictors and n are the observations (n x p matrix).

for lasso, calculating that derivative of the multiplier is not possible (for all points), so coordinated descent is used.