2
$\begingroup$

I have to prove:

$O(x)+O(x^2)=O(x^2)$ for $x\to\infty$ where "O" is the Big-O-Notation

Specific functions are no problem for me, but I have some difficulties with this general form. But nevertheless I tried the following:

$O(x)$ means $|f_1(x)|\leq |C_1 \cdot g_1(x)|$ with $g_1(x)=x$, and $O(x^2)$ means $|f_2(x)|\leq |C_1 \cdot g_2(x)|$ with $g_2(x)=x^2$ So we get $C_1 x + C_2 x^2 \leq (C_1+C_2) x^2$, which is $O(x^2)$ with $C_3=C_1+C_2$.

Is this start ok or its a big fault? Any hint would be nice.

  • 1
    Assuming that all of this is as $x\to\infty$, it seems to me that you have the right idea.2012-01-19
  • 0
    Oh sorry, I forgot $x \to \infty$. I added it. Thanks2012-01-19
  • 1
    When you say "$C_1 x + C_2 x^2 \leq (C_1+C_2) x^2$" I would be happier if you added "if $x \ge 1$"2012-01-19
  • 1
    @Daniel: Your proof looks good to me also. Depending on the meticulousness of your professor, it may be necessary to explicitly state why you're allowed to write $x \leq x^2$.2012-01-19
  • 0
    Ah ok thanks, I'll add it: I have aother problem to solve: $O(x)=O(x)-O(x), x \to \infty$. It's absolutly the same procedure or do I have to add some attributes for my $C_3$?2012-01-19
  • 1
    As far as the last problem goes, just note that the minus sign is a distraction since you're taking absolute values.2012-01-19
  • 0
    So nothing to worry about, thanks a lot :-)2012-01-19

1 Answers 1

3

$f(x) = O(g(x)) \space \leftrightarrow \exists c_1,x_0\in\mathbb{R}\space such\space that\space\forall x>x_0\space we \space have\space|f(x)| \leq C_1*|g(x)|$so if $f(x) = O(g(x))and\space for \space constant \space k\in\mathbb{R}\rightarrow O(k*f(x)) = O(g(x))$ and for $x>k$ so we have $O(g(x))\le O(x*f(x))$ so $O(g(x)) +O(x*O(g(x))) \le O(x*O(g(x)))+O(x*O(g(x))) (1)\space and\space O(x*O(g(x))) = O(2*x*O(g(x))) (2)$ from (1) and (2) : $O(g(x))+O(x*O(g(x))) = O(x*O(g(x)))$ and now put g(x) = x. the rest is prove of the following sentence and it's very easy you do it yourself as an exercise: $O(x*O(x)) = O(x^2)$