Chapter 1, Building Abstractions with Procedures

Section - Procedures and the Processes They Generate

Exercise 1.15


We can see that the procedure keeps on dividing the angle, by until it becomes less than . Clearly at max number of times the division is required is .

Thus the time complexity is .

Also since the procedure is recursive process and the maximum depth it reaches is , the space complexity is also .

To find number of steps for , we can see: ,
,
,
,
.

Thus we have to divide times. Thus is called times.