1

I'm having trouble forming a mathematical proof for a question. I can write down thousands of examples with various values of n that shows it's correct, but I'm not sure how to turn that into a mathematical proof it when multiple functions are involved.

$f_{1}, f_{2}$ and $f_{3}$ are functions on positive real numbers. Prove that if $f_{1}(n) \in O(f_{2}(n))$ and $f_{2}(n) \in O(f_{3}(n))$ then $f_{1}(n) \times f_{2}(n) \in O(f_{3}(n)^{2})$

Yuki
  • 11
  • You should write down what each of the three statements means, it may become obvious to you if you look at them together. – MPW Mar 23 '14 at 12:14
  • Expand out the definition of big-O notation and convert the big-O statements to inequalities. – user2357112 Mar 23 '14 at 12:19

2 Answers2

1

Hint:

$$\begin{cases}\left|\frac{f_1(n)}{f_2(n)}\right|\le M_1\\{}\\\left|\frac{f_2(n)}{f_3(n)}\right|\le M_2\end{cases}\;\;\implies \left|\frac{f_1(n)f_2(n)}{f_3(n)^2}\right|=\left|\frac{f_1(n)}{f_3(n)}\right|\left|\frac{f_2(n)}{f_3(n)}\right|\le \ldots\ldots?$$

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • Sorry, I'm still completely lost. My highest education is high school but I've read a bit about mathematical induction and could do the simpler examples from the mathematical induction page. Could you explain each of the steps for this answer so I can follow through? Right now I'm kinda lost. Why are we dividing f1 / f2? What is M1 and M2? How do we handle the "is in" sign instead of the equals sign? Sorry about having all these questions :( – Yuki Mar 23 '14 at 12:40
  • @Yuki, do you know what $;f=\mathcal O(g);$ means? If you don't then we're talking nonsense here. Perhaps you should first google "big O notation" and then come back. – DonAntonio Mar 23 '14 at 12:41
  • I do! I can reason about and give complexities for algorithms, but I have issues working through proofs (as above). – Yuki Mar 23 '14 at 12:47
  • @Yuki But then I can't understand why you ask about $;M_1,M_2;$, the division and stuff...! Please do write what is your definition of $;f=\mathcal O(g);$ ... – DonAntonio Mar 23 '14 at 12:49
  • Spent a while trying to understand it, and I kind of have it. I guess my question right now is how does http://puu.sh/7GgDK/cf17606602.png? Shouldn't they both by divided by $f_{3}$? Also, what should we put on the right hand side of the equality? Thanks so much for your help! – Yuki Mar 23 '14 at 13:03
  • Yes, that was a typo: both are divided by $;f_3;$ in the right side. – DonAntonio Mar 23 '14 at 13:06
  • Okay, that's awesome! I'm understanding it a bit better now. Would $f_{3}(n)^2$ go on the other side of the equality where you have the dots? – Yuki Mar 23 '14 at 13:18
  • @Yuki: perhaps if you noted that $$\left|\frac{f_1(n)}{f_3(n)}\right| =\left|\frac{f_1(n)}{f_2(n)}\right|\left|\frac{f_2(n)}{f_3(n)}\right|$$ so that $$\left|\frac{f_1(n)f_2(n)}{f_3(n)^2}\right| =\left|\frac{f_1(n)}{f_2(n)}\right|\left|\frac{f_2(n)}{f_3(n)}\right| \times\left|\frac{f_2(n)}{f_3(n)}\right|$$ things might be clearer. – robjohn Mar 23 '14 at 14:19
0

So we have three functions, all of them defined (and positive, for simplicity) for sufficiently large $x\in{\mathbb R}$.

The statement $f_1(x)=O\bigl(f_2(x)\bigr)$ means the follwing: There is a $C_1$ and an $x_1$ such that

$$f_1(x)\leq C_1 f_2(x)\qquad(x>x_1)\ .$$ Similarly, $f_2(x)=O\bigl(f_3(x)\bigr)$ means that there is a $C_2$ and an $x_2$ such that $$f_2(x)\leq C_2 f_3(x)\qquad(x>x_2)\ .$$ Then for $x>\max\{x_1,x_2\}$ we have $$f_1(x)\>f_2(x)\leq C_1 f_2(x)\cdot C_2f_3(x)\leq C_1C_2 f_3(x)\cdot C_2 f_3(x)=C\bigr(f_3(x)\bigr)^2$$ with $C:=C_1C_2^2$. This proves the claim.

Christian Blatter
  • 226,825