Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 0 down vote accepted

You can't just set all powers to the max power, because one of the coefficients of a smaller power might be equal to and of opposite sign of the coefficient of the largest power.

The purpose of the result is to show that the function grows, for large enough argument, to the same order as the term with largest exponent.

This allow you to show that the function is non-zero for large arguments and, eventually, prove the fundamental theorem of algebra.

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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