# 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: