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)))$