Proving Big Omega of a polynomial without limits
-
05-11-2019 - |
Pergunta
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?
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange