# Proof for asymptotic tight bound when $C=a_k/2$

In an algorithms lecture in school theres a proof for asymptotic tight bound like:

Take $C=a_k/2$ and show that $f(n) \ge \frac{a_k}{2} n^k$ when $n > N$ for some $N$.

\begin{align} f(n) &= a_k n^k + a_{k-1} n^{k-1} + ... + a_1 n + a_0 \\ &= \frac{a_k}{2} n^k + (\frac{a_k}{2k} n^k + a_{k-1} n^{k-1})+ ... + (\frac{a_k}{2k} n^k + a_{1} n) + (\frac{a_k}{2k} n^k + a_0) \\ &= \frac{a_k}{2} n^k + (\frac{a_k}{2k} n + a_{k-1})n^{k-1} + ... + (\frac{a_k}{2k} n^{k-1} + a_{1}) n + (\frac{a_k}{2k} n^k + a_{0}) \end{align}

We want all terms $(\frac{a_k}{2k} n + a_{k-1}), ..., (\frac{a_k}{2k} > n^k + a_0)$ to be positive. Thus we take $N=max(−2ka_{k−1} /a_k , ..., > −2ka_1 /a_k , −2ka_0 /a_k , 1)$. For any $n>N$, all previous terms are positive. Thus $f(n) > \frac{a_k}{2} n^k$ for all $n>N$ and $f(n) \in > \Omega(n^k)$

But can anyone explain simply the purpose of this? Just in a previous slide theres a simpler proof just taking the absolute value of each coefficient and setting all powers to be the max power in the expression. Why is that insufficient?

Also I dont understand whats it trying to do actually ...

-

You readily show that, by similar means, if $f(x) = \sum_{k=1}^m a_k x^{c_k}$ where $a_m > 0$, and $c_k > c_{k-1}$ for all $k$, then, for any $\epsilon > 0$, $f(x) > (a_m-\epsilon)x^{c_m}$ for all large enough $x$.