0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Thanks, that was quite useful. $\endgroup$
    – Newb
    Feb 22, 2014 at 7:37
  • $\begingroup$ Actually, I think your step "implying that $log_2 (M) + log_2 g(x) \le log_2(M)*log_2 g + log_2 g(x) = (1+M) log_2g(x)$" does not follow. The approach of the answer is correct, but that particular detail is not. $\endgroup$
    – Newb
    Feb 23, 2014 at 6:48
  • $\begingroup$ $$log_2 g \ge 2 $$ for all x implying that $$log_2 (M) < log_2(M) * log_2 g $$. Every positive constant value will be less that 2 times the constant $\endgroup$
    – eyphka
    Feb 23, 2014 at 22:52
  • $\begingroup$ No, what I meant was that specifically $log_2(M)*log_2 g + log_2 g(x) = (1+M) log_2g(x)$ is not quite correct. $\endgroup$
    – Newb
    Feb 23, 2014 at 23:27
  • $\begingroup$ Oh woops you are quite correct. $\endgroup$
    – eyphka
    Feb 23, 2014 at 23:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .