Как доказать Биг-омегу для общего полиномиального случая?

Question

Определение большого омега (Ω) таково:

Функция f (n) = Ω (g (n)), если существуют положительные постоянные c и n0, такие что f (n)> = c* g (n) для всех n, n> = n0.

Здесь одна теорема.

Я хочу доказатьthis, без использования «limit» .Я могу найти простой в использовании предел.

Я много часов думаю и ищу в интернете, но не могу его найти.Просто ограничьте ... Пожалуйста, помогите мне!

Answer 1

|Am.n^m + Am-1.n^m-1 + … A1.n + A0| <= n^m (|Am| + |Am-1|/n + … + |A1|/n^m-1 + |A0|/n^m)

Выберите несколько n0 и установите

c = (|Am| + |Am-1|/n0 + … + |A1|/n0^m-1 + |A0|/n0^m).

Это гарантирует, что

n >= n0 implies |f(n)| <= c.n^m

, поскольку c(n) < c(n0).