Доказательство большой тэты для полиномов с использованием количественного определения

Question

Как я могу доказать Большую Тету, используя количественное определение?Я знаю, что вам нужно найти 2 константы, такие, что c1 * g (n) <= f (n) <= c2 * g (n) - но как вы найдете эти константы?</p>

Может ли кто-нибудь помочь мне доказать следующее, чтобы показать пример 5x3 - 7x2 + 5x + 1 = Θ (x3)?

Answer 1

Давайте предположим, x > 0, что обычно является тем, что мы имеем.

5x^3 − 7x^2 + 5x + 1 <= 5x^3 + 5x + 1
                     <= 5x^3 + 5x^3 + x^3          ; x >= 1
                      = 11x^3

С другой стороны

5x^3 − 7x^2 + 5x + 1 >= 5x^3 - 7x^2
                     >= 5x^3 - 4x^3                ; if 7x^2 <= 4x3, i.e. x >= 7/4
                      = x^3

В заключение, для x >= 7/4 имеем:

x^3 <= (5x^3 − 7x^2 + 5x + 1) <= 11x^3

и мы закончили.