I was required to prove that the relation $S=\{(f,g)\in\mathcal{F}\times\mathcal{F}|f\in O(g)\}$ where $\mathcal{F} = \{f|f:\mathbf{Z^+}\rightarrow \mathbf{R}\}$ is not antisymmetric i came up with the following example $f=x^2$ and $g=2x^2$. This got me thinking is it true that given any two polynomials of the same degree they are big-$O$s of each other and if so would it be a worth-while excercise for some one of a novice's background to prove this conjecture?
Asked
Active
Viewed 57 times
1
-
By $f\in O(g)$ you mean that $f(x)\leq Cg(x)$ for some constant $C\in\mathbb R$ as $x\to 0$? – Inzinity Jun 23 '17 at 23:42
-
$f\in O(g) \Leftrightarrow \exists a\in\mathbf{Z^{+}}\exists c\in\mathbf{R^{+}}\forall x>a(|f(x)|\leq c|g(x)|)$ – atifcppprogrammer Jun 23 '17 at 23:52
-
The equivalence relation $f \in O(g) \wedge g \in O(f)$ is important enough to be named: $f \in \Theta(g)$. And a lot of practical asymptotic analysis is actually looking for a $\Theta$ class for the runtime of an algorithm, not just a big-O class. – Daniel Schepler Jun 24 '17 at 00:29
-
I was not aware of that thanks – atifcppprogrammer Jun 26 '17 at 05:48
2 Answers
1
Yes, your conjecture is correct!
If you have two polynomials of order $n$, i.e., $f(x) = \sum_{i=1}^nc_ix^i$ and $g(x) = \sum_{i=1}^nd_ix^i$ with $c_n\neq 0\neq d_n$, then the intuition is that for large $x$, the terms $c_nx^n$ and $d_nx^n$ will dominate, and that the other terms are negligable. Then you will have \begin{align} \frac{f(x)}{g(x)} \sim \frac{c_nx^n}{d_nx_n} = \frac{c_n}{d_n} \end{align} as $x\to \infty$ so that $2|c_n/d_n|$ (for instance) is the constant that you're looking for.
No let's be a bit more precise. You ask if it is a worthwile exercise prove it yourself, and it is, so I won't give all the details, but as a hint, you could consider the expression $f(x)/g(x)$ and devide both numerator and denominator by the relevant power of $x$. Assuming first that $c_n,d_n>0$ you want to show that there exists $\epsilon>0$ and $x_0\in\mathbb R$ such that for all $x>x_0$
\begin{align} \frac{f(x)}{g(x)} \leq \frac{c_n + \epsilon}{d_n-\epsilon} \end{align}
Then, setting $C = \dfrac{c_n + \epsilon}{d_n-\epsilon}$, you have $|f(x)|\leq C|g(x)|$ for all $x>x_0$. Alternatively you could show that both the numerator and denominator converge to a nonzero number, so that the total expression converges, from which you can also obtain a (different) $C$.
N.B. In this answer I have treated $f$ and $g$ more or less as functions $\mathbb R\to\mathbb R$, but of course the exact same reasoning applies to functions $\mathbb Z^+\to\mathbb R$.
Inzinity
- 1,733
- 11
- 22
0
Your example is fine, and your conjecture is true. If $f$ and $g$ are two polynomials of the same degree with leading coefficients $b_1$ and $b_2$, then $\frac{|f(x)|}{c|g(x)|} \to \frac{b_1}{cb_2}$ as $x \to \infty$. Choose $c$ large enough to make the limit $< 1$.
angryavian
- 89,882