# SICP Solutions: Sections 1.2.3 and 1.2.4

### Section 1.2.3 - Orders of Growth

#### Exercise 1.14

The tree is big :)

The recursive process reaches maximum depth when the denomination is a penny, for example (cc 11 1) will be $11$. This means that the growth of space will be $\Theta(n)$, where $n$ is the amount we want to change.

For each denomination sub-tree, the maximum steps we will need to calculate is where the only remaining denomination is the penny, and the steps required will be exactly $n$. Since we have $5$ denominations, the time complexity will be $O(n^5)$.

#### Exercise 1.15

##### a.

The procedure p will be applied each time angle is greater than $0.1$. Between iterations, angle will be divided by $3$. This means that with a starting angle of $12.15$ we will have p applied for $12.15, 4.16, 1.38, 0.46$ and finally for $0.15$. So p will be applied $5$ times.

##### b.

The space required will be growing on the order of $O(\log_3(n))$, because each step will require to remember its parent to return to. Similarly, the time required will be $O(\log_3(n))$ as well.

### Section 1.2.4 - Exponentiation

#### Exercise 1.16

Using the definition of even? from before:

#### Exercise 1.17

A recursive process:

#### Exercise 1.18

Similarly to exercise 1.16, we will use a variable as accumulator:

#### Exercise 1.19

First, we need to apply $T$ twice, to compute $T^2$. We start with:

\begin{align*} a &\leftarrow bq + aq + ap\\ b &\leftarrow bp + aq \end{align*}

Which will then become:

\begin{align*} a &\leftarrow (bp + aq)q + (bp + aq + ap)q + (bq + aq + ap)p\\ b &\leftarrow (bp + aq)p + (bp + aq + ap)q \end{align*}

Let’s expand the first one:

\begin{align*} a &\leftarrow (bp + aq)q + (bp + aq + ap)q + (bq + aq + ap)p\\ &= bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2 \\ &= b(2pq + q^2) + a(2pq + q^2) + a(q^2 + p^2) \end{align*}

And in the same manner the second one:

\begin{align*} b &\leftarrow (bp + aq)p + (bp + aq + ap)q\\ &= bp^2 + apq + bq^2 + aq^2 + apq\\ &= b(p^2 + q^2) + a(2pq + q^2) \end{align*}

So it turns out that we can name variables $p'$ and $q'$:

\begin{align*} p' &= p^2 + q^2\\ q' &= 2pq + q^2 \end{align*}

These values will essentially square $T$. So the logarithimic version of the Fibonacci procedure can be written as:

Updated: