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.
Asked
Active
Viewed 699 times
0
-
$|(a+b)^2|\le |(a+b)^2+(a-b)^2|=2|a^2+b^2|$ – Mario Carneiro Feb 04 '15 at 05:50
2 Answers
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.
Mario Carneiro
- 27,438
-
@user212880 Depending on the interpretation, the reverse may not be true. For arbitrarily large $x,y$ along the $x=-y$ diagonal, we have $f(x,y)=0$ and $g(x,y)>0$, so there is no $c$ such that $|g(x,y)|\le c|f(x,y)|$ for all large enough $x,y$. If we are restricting to $x,y\ge 0$, though, you have $x^2+y^2\le x^2+y^2+2xy=(x+y)^2$ so you can set $c=1$. – Mario Carneiro Feb 04 '15 at 06:26
-
It is sufficient to prove that $f\in O(g)$ to establish $O(f)\subseteq O(g)$, because $O$ is transitive, i.e. if $h\in O(f)$ and $f\in O(g)$ then $h\in O(g)$. Thus you are trying to show $f\in O(g)$ and $g\in O(f)$. My remark is pointing out that the truth of $g\in O(f)$ depends on the domain of discourse, which comes as part of the definition. If you are looking at all of $\Bbb R^2$, then $g\notin O(f)$ and the claim is false, but if it is only $[0,\infty)^2$ then the claim is true because $|g|\le|f|\le 2|g|$. – Mario Carneiro Feb 04 '15 at 06:41
