1

If we let $f(n)), g(n)$ be two non-negative and monotonically decreasing functions such that $f(n) = O(g(n))$, how can I prove that $\log_2(f(n)) = O(\log_2(g(n)))$? Is this even true in all cases? I am not sure if I am allowed to just apply the logarithm to both sides as a monotonic transformation and conclude from that that this is true.

I have a similar issue determining whether $2^{f(n)} = O(2^{g(n)})$ and whether $f(n)^2 = O(g(n)^2)$ etc. as I am unsure about the rules for transformations such as these. Could anyone provide some insight on how to go about proving or disproving these relationships?

Harrison W.
  • 777
  • Have you tried to use the definition of big O? – lanskey Mar 23 '18 at 22:06
  • @lanskey The definition implies that there exists some $c$ such that $f(n) \le c \cdot g(n)$, so $\log_2 f(n) \le \log_2 (c \cdot g(n)) = \log_2 c + \log_2 g(n)$. From this, $\log_2 c$ is just a constant so can I remove it and conclude that this statement is true? – Harrison W. Mar 23 '18 at 22:09
  • In fact you can not remove it. For that you would need to have $\log_2 c+\log_2 g(n)\leq C\log_2 c$ for some constant $C$. Which is not always possible. – lanskey Mar 23 '18 at 22:27

1 Answers1

4

Let $f$ and $g$ be two non-negative and monotonically decreasing functions such that $f=O(g)$. By definition, this means that there exists an $n_0$ and a positive real constant $M$ such that $|f(n)| \leq M|g(n)|$ for all $n\geq n_0$.

Consider $\log_2(f(n))$ for $n\geq n_0$. Since $\log_2$ is monotonic, we know that: $$\log_2(f(n)) \leq \log_2(g(n))+\log_2(M)$$

Here is where we encounter our first problem. What happens if $g(x)$ is approaching $1$ in the limit? The behavior of the upper bound of $\log_2(f(n))$ would have to be completely determined by the constant $M$, which sounds pretty absurd, and we have no information at all on the lower bound. For example, lets take $f(n)=\frac{1}{n}$ and $g(n)=1+\frac{1}{n}$. Clearly $f=O(g)$, but $|\log_2(f(n))|=\log_2(n)$ is unbounded, while $M|\log_2(g(n))|$ tends to $0$ in the limit, for any constant $M$.

For the case of considering $2^{f(n)}$ you again run into difficulties; $2^{Mg(n)}$ and $M2^{g(n)}$ might not be comparable in the direction you want. You can say for sure that $f^2=O(g^2)$, as this follows from more general properties of sums and products behaving nicely with respect to big O notation.

Valborg
  • 181