# SICP 1.2 exercises cont. 4

**Posted:**January 10, 2013

**Filed under:**Improving, SICP Leave a comment

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

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