6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 4.3.8 Using different processes for the same goal You could run the substitution model on this procedure to both verify that it works, and to determine its growth pattern However, the form is very familiar, and we can thus deduce by Space e(n)-linear Time e(n)-linear comparison to factorial that this procedure has linear growth in both space and time. The time is easy to see: there is one additional step for each increment in the size of the And fo see that there is one deferred operation for each recursive call of the procedure, so we will stack up a linear number of such deferred operations until we get down to the base case, at which point we can start completing the deferred multiplications and gathering up the Slide 4.3.9 Using different processes for the same goal As we saw earlier, we expect there are other ways of creating Are there other ways to decompose this problem? procedures to solve the same problem. With factorial, we use Use the idea of state variables. and table evolutio the idea of a table of state variables, with update rules for hanging the values of those variables. We should be able to do the same thing here terative algorithm to compute a b as a table Slide 4.3.10 So recall the idea of our table. We set up one column for each In this table One column information used piece of information that we will need to complete a step in the computation, and we use one row for each such step. The idea here is pretty straightforward. We know that a to the bth power is just b successive multiplications by a. So we can just do the multiplication, keep track of the product accumulated so far, and how many multiplications we have left. Thus after one step, we will have a product of a and b-l things left to do6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 4.3.8 You could run the substitution model on this procedure to both verify that it works, and to determine its growth pattern. However, the form is very familiar, and we can thus deduce by comparison to factorial that this procedure has linear growth in both space and time. The time is easy to see: there is one additional step for each increment in the size of the argument. And for space, we see that there is one deferred operation for each recursive call of the procedure, so we will stack up a linear number of such deferred operations until we get down to the base case, at which point we can start completing the deferred multiplications and gathering up the answer. Slide 4.3.9 As we saw earlier, we expect there are other ways of creating procedures to solve the same problem. With factorial, we used the idea of a table of state variables, with update rules for changing the values of those variables. We should be able to do the same thing here. Slide 4.3.10 So recall the idea of our table. We set up one column for each piece of information that we will need to complete a step in the computation, and we use one row for each such step. The idea here is pretty straightforward. We know that a to the bth power is just b successive multiplications by a. So we can just do the multiplication, keep track of the product accumulated so far, and how many multiplications we have left. Thus after one step, we will have a product of a and b-1 things left to do