1
$\begingroup$

You are given functions $f$ and $g$ such that $f(n)=O(g(n))$. Show that $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.

My solution: There exists $c_1$ such that $f \leq c_1 g$. Note that all $\log$ functions are base 2 throughout.

We have that $f \log(f^c) \le c_1 c g \log(c_1g) = c_1 c g \log(c_1) + c_1 c g \log(g)$.

Let expression $(*)$ be as follows:

$(*) \quad c_1 c g \log(c_1) + c_1 c g \log(g) \le c_2 g \log(g)$ for some $c_2 > 0$.

Then $(*)$ holds iff $c_1 c g \log(c_1) < 0$ iff $0 \leq c_1 \leq 1$.

Now put $c_2 = c_1 c$, then:

$c_2 g \log(c_2 / c) + c_2 g \log(g) \le c_2 g \log(g)$ iff $c_2 / c > 1$.

Therefore, we require than $c_2 > c$, which we cannot guarantee as we have already fixed $c_2 = c_1 c$.

What choice of $c_2$ would guarantee that $c_2 g \log(c_2 / c) + c_2 g \log(g) \le c_2 g \log(g)$?

I am looking for a formal argument.

$\endgroup$
1
$\begingroup$

An essential hint: "Assume that f and g are nondecreasing". That is essential. Without it the statement is false, for example $f (n) = 2$ and $g = 1 + 2^{-n}$, where log f (n) = 1 and log g (n) ≈ $2^{-n}$.

The problem here is showing that f (n) = O (g (n)) implies log f (n) = O (log (g (n)). So how does "g is non-decreasing" help? Well, if n ≥ N then 1 < g (N) ≤ g (n) and 0 < log g (N) ≤ log g (n).

f (n) = O (g (n)) means "there are $N, c > 0$ so that we have $f (n) ≤ c·g (n)$ for $n ≥ N$". So there are $N, c > 0$ so that $\log f (n) ≤ c + \log g (n)$ for $n ≥ N$. Now we need to somehow relate c and $\log g (n)$. We have $c = (c \div \log g (N)) · \log g (N) ≤ (c \div \log g (N)) · \log g (n)$, because $g (n)$ is not decreasing. Therefore $\log f (n) ≤ (c \div \log g (N) + 1) · \log g (n)$, so we found a constant c' = (c / log g (N) + 1) such that $\log f (n) ≤ c' · \log g (n)$ for n ≥ N and that means $\log f (n) = O (\log (g (n))$.

$\endgroup$
  • $\begingroup$ Thanks! If f and g were those functions, we are forced to choose $c_1>1$ so that $log(c_1)$ is positive and then the statement would not hold. Are there conditions on $c_1$ which hold due to the fact that f and g are non decreasing functions? $\endgroup$ – Ryan J. Shrott May 24 '17 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.