SICP 1.2 exercises cont. 4Posted: January 10, 2013
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!