sicp-ex-1.15



<< Previous exercise (1.14) | sicp-solutions | Next exercise (1.16) >>


The expression (sine 12.15) will be expanded by the interpreter as follows.

  
 (sine 12.15) 
  
 (p (sine 4.05)) 
  
 (p (p (sine 1.35))) 
  
 (p (p (p (sine 0.45)))) 
  
 (p (p (p (p (sine 0.15))))) 
  
 (p (p (p (p (p (sine 0.05)))))) 
  
 (p (p (p (p (p 0.05))))) 
  

We can see that the procedure p is applied five times.

The angle a is divided by 3 each time the procedure p is applied. Expressing this differently, we can say that p is applied once for each complete power of 3 contained within the angle a. Therefore, given a positive argument, we can compute the number of times p is applied as the ceiling of the base 3 logarithm of the argument divided by 0.1, or (ceiling(/ (log (/ 12.15 0.1)) (log 3)))

If we measure the required space and the number of steps by counting the invocations of p, the order of growth of the process generated by (sine a) is logarithmic. Exactly, the number of steps required are (ceiling(/ (log (/ a 0.1)) (log 3))).

In other words we have O(log(a)) order of growth.