Chapter 1, Building Abstractions with Procedures

Section - Procedures and the Processes They Generate

Exercise 1.14


Too lazy to draw :)

We can see by looking at the procedure that space complexity is $\theta (n)$ as the deepest path of the tree can have at max $n$ nodes.

I am not able to solve for time complexity. Although we can easily see that time complexity will always be less than $2^n$ as each step is divides into two branches and the maximum depth of the tree will be $n$.

Please help, if you have solution for it.