I just started learning asymptotic notation and I have a problem with this one.
Let $p(x)=a_dx^d+a_{d-1}x^{d-1}+.....+a_1x+a_0$ be a polynomial of degree d, with $a_i \in \mathbb{R}$ for $0\leq i \leq d$ and $a_d \geq 0$. Show that $p(x) \in \Theta(x^d)$
I need to show that $\exists c_1,c_2 \in \mathbb{R}, \exists x_0 \in \mathbb{R}: \forall x \geq x_0: c_1x^d \leq p(x) \leq c_2x^d$.
I initially thought that for the $p(x) \in O(x^d)$ case I could take $c_2 = d$, since $a_d \geq 0$ and thus $a_dx^d \gt a_ix^i$ for $i \in \{0,....,d-1\}$, but I don't think this has to be the case since the $a_i$'s are not restricted and any $a_ix^i$ could then easily be made larger than $a_dx^d$ simply by picking a sufficiently large value for $a_i$?!
Also for the $p(x) \in \Omega(x^d)$ case, I have a problem with the coefficient other than $a_d$ possibly being smaller than 0.
Can anybody help me out please?
Consider the limit of $\frac{p(x)}{x^d}$ as $x \to 0$. Since this equals $a_d + \frac{a_{d-1}}{x} + \cdots + \frac{a_0}{x^d}$, the limit is $a_d$. (I assume you are allowed to use limit laws?)
Pick your favorite $\epsilon > 0$ such that $\epsilon < a_d$. By the definition of limit, there is an $N$ such that $$x > N \implies \left| \frac{p(x)}{x^d} - a_d \right| < \epsilon$$ If we pick our $N > 0$, then we can rewrite the implication as $|p(x) - a_d x^2| < \epsilon x^d$, which can be expanded to $(a_d - \epsilon)x^d < p(x) < (a_d + \epsilon)x^d$. This is nearly what we want!
Let $x_0 = N + 1$, $c_1 = (a_d - \epsilon)$, and $c_2 = (a_d + \epsilon)$. Note that $c_1, c_2 > 0$. If $x \ge x_0$, then $x > N$. Therefore $(a_d - \epsilon)x^d < p(x) < (a_d + \epsilon)x^d$, and so $c_1 x^d \le p(x) \le c_2 x^d$.
See if you can prove the general theorem: $$\lim_{x \to \infty} \frac{f(x)}{g(x)} \ne 0, \textrm{ finite} \implies f(x) \in \Theta(g(x)) $$ The proof is very similar to what I've written above. The converse is nearly true, but there are counterexamples of an interesting nature.