6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology the asymptotic limit. We say that r(n) has order of growth, Theta of f of n if we can find a function f(n) that is oughly of the same order as the needed resource, where the more formal definition is shown in the Slide 4.1.8 Partial trace for (fact 4) In more common terms, this says that when measuring the amount of space we need, we want to find a function that measures the number of deferred operations, as a function of the size of the problem, up to a constant factor. For measuring the amount of time we want to find a function that measures the number of basic or primitive steps that the rewrite rules go through, again as a function of the size of the problem 6001 SKP Slide 4.1.9 Partial trace for(fact 4) So let's use our rewrite rule idea, together with this notion of measuring the amount of resource we need as an order of a(if (=n 1)i bda(n) n(act(-n1)))) growth in the size of the problem. Here is our recursive factorial 1)1《·4《aet(-41)))) 4(·3(·2(11)1(·1《tact(-11))))))) 4(·32)) 6 001 SICP Partial trace for (ifact 4) Slide 4.1.10 (define ifact -helper (lambda (product count n) and here is a partial trace of fact using those rewrite rules We start with (fact 4). That reduces to evaluating an if detine ifact (lambda (n) (ifact-helper 11 n))) expression. Since the predicate is not true, this reduces to 1per 11 4) evaluating the alternative statement, which is a combination of (f14)1( ifact- helper(*11)(+11)4) e 6 2 4) i difaot-helper (+1 2)(214) a multiplication and another evaluation of fact (if (3 4)2 (afaat-helper ( 2 3)(31) 4)) Notice how the orange colored lines capture the evolution of the rewrite rules. Note how(fact 4 )reduces to a deferred operation ft44)6 helper(64)(+41)4)) and an evaluation of (fact 3)and this further reduces to another irc>54)24( ifact- helper(*245)(+51)4) deferred operation and a subsequent call to fact. Notice the shape of this process: it grows out with a set of deferre operations until it reaches a base case, and then it contracts back in, completing each deferred operation. Using this, we can see that the amount of space grows linearly with the size of the argument. That is, with each increase in the argument size, I add a constant amount of space requirement. In terms of the number of operations, we can see that we basically need twice as many steps as the size of the problem, one to expand out, and one to reduce back down. This is also a linear growth, since the constant 2 does not change with problem size6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. the asymptotic limit. We say that R(n) has order of growth, Theta of f of n if we can find a function f(n) that is roughly of the same order as the needed resource, where the more formal definition is shown in the Slide 4.1.8 In more common terms, this says that when measuring the amount of space we need, we want to find a function that measures the number of deferred operations, as a function of the size of the problem, up to a constant factor. For measuring the amount of time, we want to find a function that measures the number of basic or primitive steps that the rewrite rules go through, again as a function of the size of the problem. Slide 4.1.9 So let's use our rewrite rule idea, together with this notion of measuring the amount of resource we need as an order of growth in the size of the problem. Here is our recursive factorial procedure ... Slide 4.1.10 ..and here is a partial trace of fact using those rewrite rules. We start with (fact 4). That reduces to evaluating an if expression. Since the predicate is not true, this reduces to evaluating the alternative statement, which is a combination of a multiplication and another evaluation of fact. Notice how the orange colored lines capture the evolution of the rewrite rules. Note how (fact 4) reduces to a deferred operation and an evaluation of (fact 3) and this further reduces to another deferred operation and a subsequent call to fact. Notice the shape of this process: it grows out with a set of deferred operations until it reaches a base case, and then it contracts back in, completing each deferred operation. Using this, we can see that the amount of space grows linearly with the size of the argument. That is, with each increase in the argument size, I add a constant amount of space requirement. In terms of the number of operations, we can see that we basically need twice as many steps as the size of the problem, one to expand out, and one to reduce back down. This is also a linear growth, since the constant 2 does not change with problem size