Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 1 / e / Solution

For a nonnegative integer parameter $n$, make both branches of a structural recursion execute:The semicolon sequences two calls, so this is not a conditional choosing just one branch. The recursion tree has $2^n$ leaves and $2^{n+1}-1$ calls. Its time complexity satisfies $T(n)=2T(n-1)+\Theta (1)$, giving $\Theta (2^n)$. Here $n$ is the parameter specified by the question, not its binary encoding length; only $\Theta (n)$ calls are simultaneously on the stack.