Exercise 1.14

Wed, Oct 28, 2020

This the 14th exercise in Sicp. Here, we draw a tree of the count-change procedure, and find how the space required and the number of steps grows.

The Question

Exercise 1.14: Draw the tree illustrating the process generated by the count-change procedure of Section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

My Thoughts

I feel we should have a quick recap of what is order of growth.

Why do we need order of growth

When a program is run, tons of factors affect the running time of a code on a machine such as OS load, OS scheduling, implemented atomic operations on CPU ets. So Scientists, could not Analalyze an algorithm simply by measuring the time a computation takes. Hence, they came up with the theoretical definition of order of growth.

What is n?

One thing for sure impacting running time and that is the input of the code, usually noted by n. Since n can be very large, these notations are also known a asymptomatic notations. So when we talk about we assume n is arbitrarily large (we don’t care about small input size).

What is considered as a step

If you look at Sicp’s explanation, you will notice that there is no explanation for what is considered a step. Therefore, I will try to give an explanation of what is my understanding.

Here is an example with 1 atomic step:

(define a (+ c b))

It has a summation and an assignment. Another example in python:

for i in range(n):
    print(i)

This has n atomic steps as print will be run n times.

Consider this example:

for i in range(n):
    for j in range(n):
        print(j)

Here the number of atomic steps are $n^{2}$.

Now consider this example:

for i in range(n):
    for j in range(i, n):
        print(j)

If n was 5, in the first iteration, there would 5 steps. In the second, 4. In the third, 3 etc. And thus we can form the general formula that the number of steps would be $\frac{n \times (n + 1)}{2}$ If you calculate that formula, you will get $\frac{n^{2} + n}{2}$.

What is Order of Growth of Steps

Now Order of Growth of Steps is an approximation of how the number of steps increase. Now, the reason I say an approximation is because we only want how it grows - Wheter if the number of steps increase or linearly, or quadratically, ($n^{2}$) or logaritmically ($\log n$).

Essentially we take the Degree of our “formula”. Take our last example:

$$ \frac{n^{2} + n}{2} $$

We see the degree of this Polynomial is 2 So we say that the Order of Growth is $\thetha(n^{2})$.

Look at the 3rd Example - it has n steps. So the Order of Growth is $\thetha(n)$