I have these two questions. I tried answering them, but got them wrong and I don't know how to answer them correctly. This is not homework --- I'd appreciate a solution (at least to one), and an explanation of how to do these proofs. I don't entirely understand the way in which big-O notation is being used here.
Consider nonnegative functions $f$ and $g$ such that $f = O(g)$, with $g(n) \geq 2$ for every $n$. Prove, or give a counterexample:
a) $\log_2f = O(\log_2 g)$
b) $2^f = O(2^g)$
As an aside, when doing any kind of math, make sure you have a strong grasp of the definitions. This means that for any proof you should write out the basic definition you will be working with.
Also when trying to figure out my solutions below, I would recommend going step by step and attempting to verify, if you have trouble with any of my steps please let me know.
The definition of big o notation is as follows:
$$f(x) = O (g(x)) \ \text {iff for some positive constant M,} \ |f(x)|\le M |g(x)| \text {for all} \ x\ge x_0 $$
Since f and g are non negative, then it follows that $$f(x)\le M g(x) \text {for all} \ x\ge x_0 $$
Then it follows that for $$x \ge x_O$$ $$log_2 f(x) \le log_2 (Mg(x)) = log_2 (M) + log_2 g(x)$$ and as $$g(x) \ge 2 \ \text {for all x}$$ so $$ log_2 g(x) \geq 1 \text {for all x} $$ implying that $$log_2 (M) + log_2 g(x) \le log_2(M)*log_2 g + log_2 g(x) = (1+ log_2(M)) log_2g(x)$$ implying $$log_2 f(x) \le (1 + log_2 (M)) log_2 g(x) \text {for all} x \ge x_0 $$ thus $$log_2 f = O(log_2 g)$$
For part b, it follows that $$f(x)\le M g(x) \text {for all} \ x\ge x_0 $$ Thus for $$x\ge x_o$$ $$ 2^{f(x)}\le 2^{Mg(x)} = 2^M*2^{g(x)}$$ and so $$2^{f(x)} = O(2^{g(x)})$$