6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 4.1.11 And let's compare that our iterative factorial. Here is our code Examples of orders of growth gain, and here is a partial trace of the rewrite evolution of that FACT pr Here we see the different shape of the process, and our order of growth analysis captures that difference. In particular, there are no deferred operations, and you can see that the maximum amount of space I need at any stage, that is, the maximun amount of space used by any rewrite, is independent of the size of the problem. We say that it is constant, as it does not grow with n In terms of time, there is basically one operation for each increment in the argument, so this is again a linear order of growth Examples of orders of growth Slide 4.1.12 ·FAcT So we can formally capture this, as shown. Fact has linear Space e(n)-linear growth in space, written as shown, because the maximum Time e(n)-linear amount of space needed by any rewrite stage is a linear multiple of the size of the argument. It also has linear growth in time, ⊙(1)- constant because as we saw it takes a number of basic steps that is also a (n)-linear linear multiple of the size of the argument Room 6001 SICP Slide 4.1.13 Examples of orders of growth On the other hand. iterative-fact has no deferred FACT operations, and is constant in space, written as shown, while as Space e(n)-linear we argued, the time order of growth is linear. Notice that the fact that the recursive version took 2n steps and the iterative version took n steps doesn't matter in terms of order of growth."P ASpTace e(1)-constant Both are said to be linear Time e(n)-linear Thus we see that we can formally characterize the difference between these two processes, which have different shapes of evolution 60015e6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 4.1.11 And let's compare that our iterative factorial. Here is our code again, and here is a partial trace of the rewrite evolution of that process. Here we see the different shape of the process, and our order of growth analysis captures that difference. In particular, there are no deferred operations, and you can see that the maximum amount of space I need at any stage, that is, the maximum amount of space used by any rewrite, is independent of the size of the problem. We say that it is constant, as it does not grow with n. In terms of time, there is basically one operation for each increment in the argument, so this is again a linear order of growth. Slide 4.1.12 So we can formally capture this, as shown. Fact has linear growth in space, written as shown, because the maximum amount of space needed by any rewrite stage is a linear multiple of the size of the argument. It also has linear growth in time, because as we saw it takes a number of basic steps that is also a linear multiple of the size of the argument. Slide 4.1.13 On the other hand, iterative-fact has no deferred operations, and is constant in space, written as shown, while as we argued, the time order of growth is linear. Notice that the fact that the recursive version took 2n steps and the iterative version took n steps doesn't matter in terms of order of growth. Both are said to be linear. Thus we see that we can formally characterize the difference between these two processes, which have different shapes of evolution