2
$\begingroup$

Here is the definition of $\Omega$:

$f(n) = Ω(g(n))$ iff there exist positive constants $c$ and $n_0$ such that $f(n) \ge cg(n)$ for all $n\ge n_0$.

Here is one theorem:

If $f(n) = a_m n^m + \cdots + a_1 n + a_0$ and $a_m > 0$, then $f(n) = \Omega(n^m)$.

I want to prove this, without using limits. Despite many hours of searching across the internet, all I could find is proofs using limits. Is there any other way?

$\endgroup$
2
$\begingroup$

Define $M = \max(|a_0|/a_m, |a_1|/a_m, \ldots, |a_{m-1}|/a_m)$, and take $c = a_m/2$ and $n_0 = 2mM$. Then for $n \geq n_0$, $$ \begin{align*} f(n) &= a_m n^m \left(1 + \frac{a_{m-1}}{a_m} \cdot \frac{1}{n} + \cdots + \frac{a_1}{a_m} \cdot \frac{1}{n^{m-1}} + \frac{a_0}{a_m} \cdot \frac{1}{n^m}\right) \\ &\geq a_m n^m \left(1 - \frac{M}{n_0} - \cdots - \frac{M}{n_0^{m-1}} - \frac{M}{n_0^M}\right) \\ &\geq a_m n^m \left(1 - \frac{mM}{n_0}\right) \\ &= c n^m. \end{align*} $$

$\endgroup$
  • $\begingroup$ I try another way, but it seems better. thanks. $\endgroup$ – js lee Mar 24 at 14:57

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.