SICP 1.2 exercises cont. 4

Sadly I skipped a day for the first time. Maybe I should keep a score.

change

Order of growth

space: O(n) because it depends on the maximum depth of the recursion tree

steps: I don’t really feel like doing a rigorous analysis here so I cheated and looked at this excellent explanation. The intuition is that the simple case where there is only one kind of coin needs O(n) steps. Each additional coin type creates O(n) steps that split into lower coin types. So we get O(n^k) where k is the number of coin types.

Comments: Talk about tedious!

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