Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 2

Problem:

You are given functions f and g such that $ f(n)=O(g(n)) $. Is $ f(n)∗\log_2(f(n)c)=O(g(n)∗\log_2(g(n))) $ ? (Here c is some positive constant.) You should assume that $ f $ and $ g $ are nondecreasing and always bigger than 1.

Solution:

Using the definition of the Big-Oh notation, we are given:

$ f(n) < c_1 g(n) $ for $ n > n_0 $.

Let's try to derive a bound for the left hand side, we have

$ \begin{eqnarray*} f(n) & < & c_1 g(n) \\ f(n)^c & < & (c_1 g(n))^c \\ \log_2(f(n)^c) & < & \log_2((c_1 g(n))^c) \\ \log_2(f(n)^c) & < & c\log_2(c_1) + c\log_2(g(n)) \\ f(n)\log_2(f(n)^c) & < & cc_1 g(n)\log_2(c_1) + cc_1 g(n)\log_2(g(n)) \\ \end{eqnarray*} $

So far, the proof is obvious:
The second line comes from the assumption that the values are bigger than 1
The third line comes from logarithm is monotonic.
The rest is just simplification of properties of log.

To simplify things further, we get $ d = cc_1 \log_2(c_1) $ and $ e = cc_1 $, so we have

$ \begin{eqnarray*} & & f(n)\log_2(f(n)^c) \\ & < & dg(n) + eg(n)\log_2(g(n)) \\ & = & g(n)(d + e\log_2(g(n)) \\ & = & g(n)(d\frac{\log_2(g(0))}{\log_2(g(0))} + e\log_2(g(n)) \\ & \le & g(n)(\frac{d}{\log_2(g(0))}\log_2(g(n)) + e\log_2(g(n)) \\ & = & (\frac{d}{\log_2(g(0))} + e)g(n)\log_2(g(n) \\ \end{eqnarray*} $

The critical line above is line 4, where we use the fact that g(n) is non-decreasing. Together we proved $ f(n)∗\log_2(f(n)c)=O(g(n)∗\log_2(g(n))) $