# Understanding why the polynomial $p(n) = \sum_{i=0}^{k} a_in^i$ is in $\Theta(n^k)$

Hi I've read this lemma in my book:

Lemma 2.1. Let $p(n) = \sum_{i=0}^{k} a_in^i$ denote any polynomial and assume $a_k > 0$. Then $p(n) \in \Theta(n^k)$

Proof. It suffices to show that $p(n) \in O(n^k)$ and $p(n) \in \Omega(n^k)$. First observe that for $n > 0$, $$p(n) \leq \sum_{i=0}^{k} |a_i|n^i \leq n^k \sum_{i=0}^{k}|a_i|,$$ and hence $p(n) \leq (\sum_{i=0}^{k}|a_i|)n^k$ for all positive $n$. Thus $p(n) \in O(n^k)$.

Let $A = \sum_{i=0}^{k-1}|a_i|$. For positive $n$ we have $$p(n) \geq a_kn^k -An^{k-1} = \frac{a_k}{2}n^k + n^{k-1}(\frac{a_k}{2}n - A)$$ and hence $p(n) \geq (a_k/2)n^k$ for $n > \frac{2A}{a^k}$. We choose $c=a_k/2$ and $n_0 = 2A/a^k$ in the definition of $\Omega(n^k)$, and obtain $p(n) \in \Omega(n^k)$.

Can anyone explain me the part $p(n)\in \Omega(n^k)$ of the proof? Why should we divide $a_k\cdot n^k$ by 2? Why can't we take $a_kn^k$ as coefficient of $n^k$? And how do we obtain that $n>2A/a_k$?

• You can't take $a_k$ as the coefficient of $n^k$ since the corresponding result could be false. For example if $p(n) = n^2 - 2n + 1$ then it is not true that $p(n) \geq n^2$ for large enough $n$. On the other hand, it is true that for every $\epsilon > 0$, $p(n) \geq (1-\epsilon) n^2$ for large enough $n$ (depending on $\epsilon$). – Yuval Filmus May 14 '13 at 23:43

The starting point is the inequality $p(n) \geq a_kn^k - An^{k-1}$. We want to deduce from this inequality that for large enough $n$, $p(n) \geq bn^k$ for some $b > 0$. So take any $b > 0$ satisfying $b < a_k$. Since $$p(n) \geq a_k n^k - An^{k-1} = \left(a_k - \frac{A}{n}\right) n^k,$$ we have $p(n) \geq bn^k$ as long as $a_k - A/n \geq b$. As $n \to \infty$, $A/n \to 0$, and so it is clear that the inequality $a_k - A/n \geq b$ holds for large enough $n$. If we want an explicit lower bound on $n$, we can do some algebra to obtain the equivalent inequality $n \geq A/(a_k - b)$.
To show that $p(n) \geq cn^k$, given that $p(n) \geq an^k - An^{k-1}$, the $k-1$ term has to be made positive. For that purpose that $an^k$ is divided into two terms. It doesn't matter much whether those terms are both $a/2$ or one is $a-\epsilon$ and another is $\epsilon$ or anything else. The final step is to find $n$, such that $n^{k-1}(\frac{a}{2} n - A) \geq 0$. Then the required inequality follows.
• What do you mean by "the $k-1$ term has to be made positive"? – Yuval Filmus May 14 '13 at 23:36
• Only that $p > a - c$ does not imply $p > a$. – Karolis Juodelė May 15 '13 at 6:54