Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 1 / e

The VAR marker passes a reference parameter, so every recursive call accesses the same array without copying it. Read-only access does not make copying necessary. Under the examination's value parameter convention, omitting VAR copies the whole actual array, not merely the selected segment $u[a..b)$.

If its length is $L$, the $\Theta (n+1)$ calls therefore cost $\Theta (L(n+1))$ for $n=b-a$. For a whole-input construction, $L=n>0$:Copying only the shrinking segments would instead lead to $\Theta (n\log n)$, but that is a different parameter passing model from passing the same actual array on every call.