# brian_hassinger

software developer

## Orders of Growth

February 06, 2013

An order of growth is a measurement of a process as the problem domain changes. A process with a growth θ(n²) is said to grow exponentially with each increase of n.

#### Exercise 1.14

Draw a tree of the `count-change` procedure.

![“Exercise 1.14”][png1.14] [png1.14]: /assets/img/sicp/1.14.png “Exercise 1.14”

Each node represents a call to the `cc` procedure. The left operand is the amount of change and the right operand is the number of coins. From every node there are two branches, the right branch subtracts the `first-denomination` from the amount of change, and the left branch reduces the number of coins. Notice `(cc 6 1)` is the largest recalculated node.

The order of growth for the space is proportional to the amount of change `n` Θ(n). The number of steps for the procedure is Θ(n²). As `n` gets larger the number of branches recalulated grows exponentially.

#### Exercise 1.15

1. How many times is the procedure `p` applied?
2. What is the order of growth?
``````;;EXERCISE 1.15
(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
``````
1. The procedure p is continuously applied until the angle is less than or equal to the explicit precision value 0.1

`````` 12.15 / 3.0 = 4.05    ; (p (sine 4.05))
4.05  / 3.0 = 1.349   ; (p (p (sine 1.349)))
1.349 / 3.0 = .4499   ; (p (p (p (sine .4499))))
.4499 / 3.0 = .15     ; (p (p (p (p (sine .15)))))
.15   / 3.0 = 4.99e-2 ; (p (p (p (p (p (sine 4.99e-2))))))
``````

The procedure `p` is called 5 times before the angle is <= the precision value.

2. The number of steps for (sine a) = Θ(log a) The size of space for (sine a) = Θ(log a)

Note: My math skills are poor. but I think the number of steps are logarithmic because as ‘a’ grows in size the number of steps get smaller. Similarly, the space is related to the number of `p` calls, so it too must be logartihmic