3
$\begingroup$

As a homework assignment I am trying to prove/disprove the next statement:

Let $f(x)=O_a(g(x))$, then $\forall A,B\in\mathbb{R}\rightarrow A\cdot f(x)=O_a(B \cdot g(x))$

Which I think is wrong and thus trying to disprove.

So assuming I'm right, my question is logical: we know that there exist a $C_1 \gt 0$ such that $\|f(x)\| \le C_1 \cdot \|g(X)\|$ for all $x$ in a neighborhood of $a$. In order to disprove the given statement, should I show that there exist $A,B\in\mathbb{R}$ such that $\|f(x)\| \gt C_1 \cdot \|g(X)\|$ for ALL $C \gt 0$, or for a specific $C_1$?

Hope I was clear, thanks

  • 0
    Since this is true whenever $B \neq 0$, I think there is a little mistake in the text.2012-05-08

1 Answers 1

1

You would have to show it for all $C$, but note that there is an implicit "for all functions $f$ and $g$" in your original assignment, so while you have to do it for all $C$, you just have to disprove it for one pair of $f$ and $g$.

But for this assignment a much better approach is to try to prove the statement. If it is true you will just succeed. If it is wrong, your proof will break down at some point which will give a hint what values of $A$, $B$, $f$ and $g$ pose the problem.

Since the statement is actually true for most values it will be very hard to find a counter-example by random trials.

  • 0
    When you try to prove the relationship with the definition of big $O$, there are only a few cases that remain. Now, to disprove the statement, you exhibit explicit values of $f$, $g$, $A$ and $B$ such that the statement is wrong.2012-05-08