0
$\begingroup$

This question already has an answer here:

How can I prove that if $T(x)$ is a polynomial of degree $n$ then $T(x) = \Theta(x^n)$.

$\endgroup$

marked as duplicate by David Richerby, Raphael Nov 21 '15 at 11:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ What have you tried and where did you get stuck? Without a specific question, this is just a duplicate of our reference question which explains general strategies of proving such claims. $\endgroup$ – Raphael Nov 21 '15 at 11:06
  • 1
    $\begingroup$ Take care of adhereing to the exact definition of $\Theta$ you were given in class. Are functions with negative values allowed? $\endgroup$ – Raphael Nov 21 '15 at 11:08
3
$\begingroup$

Say $T(x) = a_n x^n + \dotsm + a_0$, then by the triangle inequality for $x \ge 1$:

$\begin{align} \lvert T(x) \rvert &\le \lvert a_n \rvert x^n + \lvert a_{n - 1} \rvert x^{n - 1} + \dotsm + \lvert a_0 \rvert \\ &\le \lvert a_n \rvert x^n + \lvert a_{n - 1} \rvert x^n + \dotsm + \lvert a_0 \rvert x^n \\ &= (\lvert a_n \rvert + \lvert a_{n - 1} \rvert + \dotsm + \lvert a_0 \rvert) x^n \end{align}$

I'm sure you can take it from here. You'll have to figure out an appropriate lower bound to match.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.