Solution
= Solution
For input length $n$, the successive <list concatenations> copy prefixes of lengths $0,1,\ldots,n-1$. Thus $T(n)=T(n-1)+\Theta(n)$ and $T(n)=\Theta(1+\sum_{j=0}^{n-1}(j+1))$. \b[The direct implementation takes $\Theta(n^2)$ time] for a fully produced nonempty reversal. The repeated copying, rather than the number of recursive calls alone, causes the quadratic cost.