Complete the proofs for Corollary 10.1 and parts (b) and (c) of Theorem 10.2.
Corollary 10.1
Let a,b, c ∈ Z+ with b ≥ 2, and let f: Z+ → R. If
f(1) = c, and
f(n)=af(n/b) + c, for n=bk, k ≥ 1,
then
(1) f ∈ 0(logb n) on {bk|k ∈ N}, when a = 1, and
(2) f ∈ 0(nlogb a) on {bk|k ∈ N}, when a ≥ 2.
Parts (b) and (c) of Theorem 10.2.
Let f: Z+ → R+ ∪ {0} be monotone increasing, and let g: Z+ → R. For b ∈ Z+ b ≥ 2, suppose that f ∈ O(g) for all n ∈ S = {bk|k ∈ N}. Under these conditions,
(b) If g ∈ 0(n log n), then f ∈ 0(n log n).
(c) If g ∈ O(nr), then f ∈ 0(72r), for r ∈ R+ ∪ {0}.