生活習慣が(今のところ)ガラッと変わって夜に寝るのがものすごく早くなったので、当分は朝に勉強時間を設けるようにしてみます。
どういうペースでやるのがいいのか、当分は試行錯誤が続きそうです。

問題解答

問題1.14
木の展開はひたすら手を動かす問題。
オーダーについてはよくわからなかったので先人の記録を頼る(ただ、ちょいちょい間違いがあるような気がするので後述のサイトを参考にした方がよさそう)。また、そこから先に更に詳しい解説が。

cc が呼ばれる度に、 1,0 もしくは二つのサブツリーの和を返す。そして、ツリー中の各ノードでは一処理をおこなう。
amount n と kinds-of-coints が 5 の場合、処理の数は (1 + (cc n 4) の処理の数 + (cc (-n 50 5)) の処理の数)。以後、
N(n,m) を subtree (cc n m) によっておこなわれる処理の数とする。

これを踏まえて N について考える。

N(n,　5) = 1 + N(n,　4) + N((n-50), 5)
N(n,　4) = 1 + N(n,　3) + N((n-25), 4)
N(n,　3) = 1 + N(n,　2) + N((n-10), 3)
N(n,　2) = 1 + N(n,　1) + N((n-5), 2)
N(n,　1) = 1 + N(n,　0) + N((n-1), 1)

N(n,　0) = 1
N((n-1),　1) = N(n, 0) + N((n-2), 1)

(n　-　n) まで展開される。

これを後ろからのぼっていく。

N((n-n, 1) = N(0, 1) = 1
N((n-(n-1), 1) = N(1, 1) = 1 + N(1, 0) + N(0, 1) = 1 + 1 + 1 = 3
N((n-(n-2), 1) = N(2, 1) = 1 + N(2, 0) + N(1, 1) = 1 + 1 + 3 = 5
N((n-(n-3), 1) = N(3, 1) = 1 + N(3, 0) + N(2, 1) = 1 + 1 + 5 = 7

つまり、 N(n, 1) = 2n+1

よって、オーダーは Θ(n)。

同様にして N(n, 2) について考える。

N(n, 2) = 1 + N(n, 1) + N((n-5) 2)
= 1 + N(n, 1) + N(n, 1) + N((n-10) 2)

n-5x <= 0 になるまで展開されるので、ざっくり n/5 回繰り返される。 そして、N(n, 1) は Θ(n) なので Θ(n*n/5) = Θ(n^2)。 同様に N(n, 3), N(n, 4), N(n, 5) を考えると N(n, 5) のオーダーは Θ(n^5)。 うはー。一問、2行に二時間かけてもうた。。。