Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 3 / b / Solution

For input length $n$, the successive list concatenations copy prefixes of lengths $0,1,\dots ,n-1$. Thus $T(n)=T(n-1)+\Theta (n)$ and $T(n)=\Theta (1+{\sum }_{j=0}^{n-1}(j+1))$. 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.