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$?

  • 1
    $\begingroup$ 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$). $\endgroup$ – 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.

  • $\begingroup$ What do you mean by "the $k-1$ term has to be made positive"? $\endgroup$ – Yuval Filmus May 14 '13 at 23:36
  • $\begingroup$ Only that $p > a - c$ does not imply $p > a$. $\endgroup$ – Karolis Juodelė May 15 '13 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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