sicp-1-2-3-orders-of-growth

#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.