The lasso can be computed with the LARS or Coordinate Descent algorithm.
What is their computational complexity and when one is quicker than the other?
I realize it's quite late to give an answer but maybe someone will find it useful.
Here is a nice talk by Trevor Hastie about the coordinate descent. He compares (among others) his two R packages:
glmnet (using coordinate descent) and
lars (using LARS).
It's shown that coordinate descent is faster in each setting: $p>N, p<N$ and sparse or dense data. There are some examples featuring both simulated and real data.