= Solution
Write $S_j=\ell_1+\cdots+\ell_j$, with $S_0=0$. At the $j$th step of the <left fold>, the left operand of <list concatenation> is the accumulated prefix of length $S_{j-1}$. Fully forcing these concatenations repeatedly copies earlier elements. Including the traversal of the outer <list> and the whole output spine gives
$$
\boxed{T_{\mathrm{left}}=\Theta\!\left(k+N+\sum_{j=1}^{k-1}S_j\right)
=\Theta\!\left(k+N+\sum_{t=1}^{k-1}(k-t)\ell_t\right).}
$$
For singleton inner <lists>, this becomes $\Theta(1+2+\cdots+(k-1))=\Theta(k^2)$, whereas the <right fold> takes $\Theta(k)$. More generally, for equal positive length $r$, the <left fold> takes $\Theta(rk^2+k)$.
An $O(kN+k)$ bound is tight in the worst case over length distributions, but is not a tight formula for every distribution: if all $N$ elements occur only in the final inner <list>, all earlier accumulators are empty and the cost is $\Theta(k+N)$. <Lazy evaluation> changes when the work happens; it does not remove repeated prefix traversal when the whole result is demanded.
Back to article page
