What is the complexity of this algorithm for sparse matrices?
They say the running time is $O(n+|b|+f)$, where $f$ is the number of floating point operations taken during the entire computation.  This takes some careful reading to understand what they mean.

They mean, if you take the total number of floating-point operations that are performed inside the innermost loop, and call that $f$, then the running time is not too much more than $f$.  In other words, they are saying we do $O(n+|b|)$ operations for updating the loop indices, plus the time taken by the body of the innermost loop (summed over all the iterations).

The body of the innermost loop might indeed take $5 n|b|$ operations in total (say), in which case the total running time would be $O(n + |b| + 5n|b|) = O(n|b|)$, as you had expected.

Note that $f$ is not the number of floating point operations in a single iteration of the innermost loop; it is the total across all iterations of the loop.  So $f$ is not 5.

Why do they count it this way?  Presumably, the floating point operations are ones that we'll have to do no matter what, because they are essential to the operation you're doing; they instead want to focus on the extra book-keeping needed to update loop indices etc. and make sure that doesn't add too much extra cost.

Finally, I'll note that you changed the pseudocode.  The pseudocode they show is not the same as what you listed in the question.  In the book the pseudocode of the innermost loop is not "for $i=j+1$ to...", but rather "for each $i&gt;j$ for which $l_{ij}$".  That's not the same.  Since $l$ is a sparse matrix/vector, there are more efficient ways to iterate over the non-zero entries of $l$ than iterating over all possible values of $j$ and testing whether that element is non-zero.  This also affects the running time.