Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 3 / a / iii / Solution

Regardless of which branch is taken, $r(n)\le r(n-1)+n$. Starting from zero and applying induction givesFor the inductive step, add $n$ to the bound $(n-1)n/2$ for the previous value. The subtraction branch gives an even smaller result, and positivity is checked there. This bound need not describe the actual growth sharply; it is sufficient to size a finite membership representation for a requested prefix.