Problem 2.1

[aaarbk]

I think the solution to problem 2.1 is wrong. I believe the crux of the issue is that f(n) = O(g(n)) doesn't imply lg f(n) = O(lg g(n)).

A counterexample is f(n) = 2 and g(n) = 1 for all n, then f(n) lg f(n) equals 2 and g(n) lg g(n) equals 0 and we cannot bound f(n) lg f(n) from above by g(n) lg g(n). If taking constant functions feels funny, try f(n) = 2 - exp(-n) and g(n) = 1 + exp(-n).