How to justify adding and multiplying relations with big-O?

Question

I know that it's valid to add and multiply functions in Big O, although I haven't seen a proof why. As such I think this is a valid starting point. However, I have no idea how to progress and any help would be much appreciated.

Answer 1

By definition of big-$O$, we say that $f(x)\in O(g(x))$ if there is a $c,M$ such that for all $x\ge M$, $|f(x)|\le c|g(x)|$. In multiple variables this gets a little more complicated and/or ambiguous since the $M$ now becomes a bounding region instead of just a point, but luckily in this case we will have $|f(x,y)|\le c|g(x,y)|$ for all $x,y$ so we don't have to worry about $M$.

In the context of this problem, $f(x,y)=(x+y)^2$ and $g(x,y)=x^2+y^2$. Since both $f$ and $g$ are positive, we can actually drop the absolute value bars, so that $f(x,y)\in O(g(x,y))$ iff there is a $c$ such that $f(x,y)\le cg(x,y)$ for "large enough" $x,y$, say $x,y\ge M$ for some $M$ (which we can just set to $0$). Then we just need to show this algebraically:

$$f(x,y)=(x+y)^2\le (x+y)^2+(x-y)^2=2x^2+2y^2=2g(x,y),$$

so we are done.

It is very easy to forget the definition of big-$O$ and just apply heuristic rules to it (since that's what it was designed for), but in more complicated cases when the heuristics don't apply directly you should always remind yourself about the definition and how it applies so that you don't lead yourself astray.

Answer 2

if $a > b$, then $(a+b)^2 <(2a)^2 =4a^2 = O(a^2) =O(a^2+b^2) $.