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 as the deepest path of the tree can have at max nodes.

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

Please help, if you have solution for it.