SICP 1.2 exercises cont. 5

1.15

I just used the substitution method.

(sine 12.15)
(p (sine (/ 12.15 3)))
(p (sine 4.05))
(p (p (sine (/ 4.05 3))))
(p (p (sine 1.35)))
(p (p (p (sine (/ 1.35 3)))))
(p (p (p (sine 0.45))))
(p (p (p (p (sine (/ 0.45 3))))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine (/ 0.15 3)))))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p 0.05)))))

a) p is called 5 times as shown above.

b) space is O(n) as a set amount of memory is needed for each p. Number of steps I believe is also O(n) because p does not cause any branches in the recursion tree.

Edit: According to the answer here a refers to the angle, not the number of times p is called. In which case the answer to part b) is O(log n) because the number of calls to p is log_3(angle).

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s