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

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)$.

StackExchange Computer Science Q#12022, answer score: 5