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?
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.