prove that a polynomial is lower bounded

Question

I need help with this question from Data-Structure course. I need to prove that the following polynomial is lower bounded by $n^k $, meaning I need to show that: $$ p(n) = b_kn^k - b_{k-1}n^{k-1}-b_0n = \Omega(n^k) $$ So I have switched the Omega to inequlity and now I need to show that there exist constant $c$ and $n_0$ that solve the following inequality: $$ b_kn^k - b_{k-1}n^{k-1}-b_0 n \ge c \cdot n^k $$ holds for $n \ge n_0$. It is also given that $$ b_k , b_{k-1} , b_0 > 0 \,.$$

Answer 1

Let us assume you are interested in positive $n$. Since there are explicit negative signs, I also assume the $b_k \ge 0$. Now set: $$ n_0 = \max \left(\frac{3b_{k-1}}{b_k}, \sqrt[k-1]{3\frac{b_{0}}{b_k}},1\right)\,.$$

They relate to the second monomial, the last one, and the $1$ avoids divisions by zero. Basically, the $3$ factors are meant to end up with something like: $$ p(n) \ge b_k n^k -\frac{b_k}{3} n^k - \frac{b_k}{3} n^k\,,$$ to get a constructive bound. Other choices are possible.

So if $n \ge n_0$ , then $$b_{k-1} n^{k-1} = b_{k-1} \frac{n^{k}}{n}\le b_{k-1} \frac{n^{k}}{n_0} \le \frac{b_k}{3} n^k\,, $$ and similarly $$b_{0} n = b_0 \frac{n^{k}}{n^{k-1}}\le b_0 \frac{n^{k}}{n_0^{k-1}} \le \frac{b_k}{3} n^k \,.$$

Thus $p(n) \ge \frac{b_k}{3}n^k$. Finally, for $n_0$ as above, you can choose $$c = \frac{b_k}{3}\,.$$

On the notation side, it could be interesting to suppose $k \ge 2$, and a $b_1 n$ would be more consistent with your notations.

Answer 2

For any polynomial $$P(x)=\sum_{k=0}^d p_kx^k$$

and $x>0$, we have

$$\frac{P(x)}{x^d}=\sum_{k=0}^d\frac{p_k}{x^{d-k}}=p_d+\frac{p_{d-1}}x+\frac{p_{d-2}}{x^2}+\cdots\frac{p_0}{x^d}.$$

Then if $p_d>0$, we can find an $x$ large enough such that

$$-\frac{p_d}d<\frac{p_{d-1}}x,\frac{p_{d-2}}{x^2},\cdots\frac{p_0}{x^d}<\frac{p_d}d,$$ for instance $$x>\dfrac{p_d}d\max(|p_{d-1}|,|p_{d-2}|,\cdots|p_0|).$$

Then, with this value of $x$ and all larger,

$$(1-\frac{d-1}d)p_d<\frac{P(x)}{x^d}<(1+\frac{d-1}d)p_d$$

which reads

$$cx^d<P(x)<c'x^d,$$

expressing $$P(x)=\Theta(x^d).$$