= Solution
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$:
$$
\boxed{\Theta(n)\text{ with VAR},\qquad\Theta(n^2)\text{ with whole-array value copying}.}
$$
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.
Back to article page
