#lang racket
;; 1.14
;; claim: The time complexity of cc(n, d) is O(n ^ d) where n is the amount and d
;; is the number of denominations.
;; Here is a proof sketch that goes by induction on d.
;; Write n = q * d + r with 0 <= r < d.
;; Keep applying the recursive definition of cc(x, d) = cc(x, d - 1) + cc(x - d, d)
;; to rewrite cc(n, d) as a sum of terms involving only d - 1 as follows:
;; cc(n, d) = cc(n, d - 1) + cc(n - d, d)
;; = cc(n, d - 1) + cc(n - d, d - 1) + cc(n - 2 * d, d)
;; = ...
;; = cc(n, d - 1) + ... + cc(n - (q - 1) * d, d - 1) + cc(n - q * d, d)
;; = cc(n, d - 1) + ... + cc(n - (q - 1) * d, d - 1) + cc(n - q * d, d - 1)
;; where the last step uses the fact that cc(n - q * d, d) = cc(n - q * d, d - 1)
;; because n - q * d = r < d.
;; The terms of this sum are decreasing, the first term cc(n, d - 1) = O(n ^ (d - 1))
;; by induction, and there are theta(n) terms. So the sum itself must be O(n ^ d).
;; The space complexity is the depth of the recursive tree which is q and so O(n).
;; 1.15
;; The sine procedure makes a single recursive call. So the recursive tree is a
;; single branch. So the space complexity, which is the depth of the tree, will
;; be the same as the time complexity, which is the number of nodes in the tree.
;; This complexity is O(log a) because the recursion bottoms out after repeatedly
;; cutting a down by 1/3 until it is less than 0.1, which is log3(10 * a) steps.
Comments