What we aim to prove is that if we have a polynomial $f(x)$ of degree $n$, then $f(x) = O(x^n)$, which is equivalent to
$$\exists k>0\;\exists x_{0}\;\forall x>x_{0}\;|f(x)|\leq k x^n$$
We know that
$$|f(x)| = |\sum _{i=0} ^{n}{a_i x^i}| \leq \sum _{i=0} ^{n}{|a_i| |x^i|}$$
by the triangle inequality (I'm not sure if it holds for $n$ variables).
Now notice that if $x > 1$ the following always holds
$$\forall a, b \in \mathbb{N} \; a \geq b \Rightarrow x^a \geq |x^b|$$
Therefore we know that for $x>1$
$$|f(x)| \leq \sum _{i=0} ^{n}{|a_i| |x^i|} \leq x^n \sum _{i=0} ^{n}{|a_i| }$$
And so if we set $k = \sum _{i=0} ^{n}{|a_i|}$ and $x_0=1$ the theorem is proved.
I'm not sure if this line of reasoning is correct, mostly because of the triangle inequality. Also, this seems rather complicated. Is there a more elegant proof of this fact?
Edit: Also, I'm not really sure how to prove this for $\Omega(x^n)$ and therefore also for $\Theta(x^n)$ since I cannot use the triangle inequality like in the proof for $O(n)$
Best Answer
Here is an alternative approach (and how I like to think of it). Note that $\lim_{x\to\infty} f(x)/x^n=a_n\neq 0$ and hence $\lim_{x\to\infty} |f(x)/x^n|=|a_n|.$ Now choose $\epsilon=|a_n|$, then there exists an $x_0$ such that for all $x>x_0$, we have $|f(x)/x^n|\in (|a_n|-\epsilon, |a_n|+\epsilon)=(0,2|a_n|)$, which means $|f(x)|< 2|a_n|x^n$.