Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hello can somebody help me in expressing $x^3/1000 - 100x^2 - 100x + 3$ in big theta notation. It looks like of $x^3$ to me, but obviously at $x =0$ obviously this polynomial gives a value of $3$. And multiplying $x^3$ by any constant won't help at all. Is there a standard way to approach such kind of problem?

share|improve this question
add comment

2 Answers 2

As a general rule, "$f(x)$ is $\Theta(g(x))$" means "$f(x)$ is $\Theta(g(x))$ as $x \to \infty$." So you're allowed to ignore any finite number of zeroes of $f$ and $g$ -- you just have to show that each one is bounded by a constant multiple of the other if $x$ is big enough.

share|improve this answer
add comment

More generally, given an arbitrary real polynomial $p(x)=a_nx^n+\cdots+a_1x+a_0$ with $a_n>0$, let us denote by $M$ a number greater than all of $p$'s real roots. We have

$$\lim_{x\to\infty}\frac{p(x)}{x^n}=a_n+a_{n-1}(0)+\cdots+a_1(0)+a_0(0)=a_n>0.$$

Now $p$ is continuous and has no roots beyond $M$ so it cannot change sign beyond $M$; at the same time the limit is positive so it must be the case that $p(x)>0$ for all $x>M$. Also, $x^{-n}p(x)-a_n$ tends to zero as $x\to\infty$ and has no singularities so it must be bounded, hence also given $0<L<a_n$ there is some $N$ such that it is $\le L$ in magnitude for all $x>N$ (by the definition of a limit at infinity).

Claim:

$$-L+a_n\le \frac{p(x)}{x^n}< a_n+\frac{|a_{n-1}|}{M}+\cdots+\frac{|a_1|}{M^{n-1}}+\frac{|a_0|}{M^n} \quad \text{for all }x>\max\{M,N\}.$$

Proof. The left inequality follows from hypothesis on $-L$ being a lower bound. Otherwise for $x>M$ we have that $a_k<|a_k|$ and $1/x^\ell<1/M^\ell$; the latter is because $x\mapsto 1/x^\ell$ is a decreasing function on $x>0$ for $\ell>0$, and since the latter involves positive quantities it may be multiplied by the former (see here and adapt as necessary), hence $a_k/x^\ell <|a_k|/M^\ell$. Apply this to each term in $p(x)/x^n$ and then add the inequalities together to get the right-hand inequality above.

This demonstrates that $p(x)/x^n$ is squeezed between two positive reals for sufficiently large $x$; multiply both sides by $x^n$ and we have shown $p(x)$ fulfills the definition of $\Theta(x^n)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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