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?
expressing $x^3 /1000 - 100x^2 - 100x + 3$ in big theta
2 Answers
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.
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
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)$.