Если мы попытаемся найти положительную постоянную c такую, что
(1/100)n^3 - 100n^2 - 100n + 3 >= cn^3
, мы потерпим неудачу, потому что для малых значений n левая часть отрицательна (например,n=1).
Но нам это не нужно! Нам нужно удерживать неравенство, когда n выше некоторого порога n0.Итак, давайте помнить об этом, работая над упрощением нашего выражения.
(1/100 - c)n^3 - 100n^2 - 100n + 3 >= 0 ; group by degree!
iff
(1/100 - c)n^3 >= 100n^2 + 100n - 3
if
(1/100 - c)n^3 >= 100n^2 + 100n ; easy but effective
if
(1/100 - c)n^3 >= 100n^2 + 100n^2 ; key simplification!
= 200n^2
если
(1/100 - c)n >= 200
если
((1 - c)/100)n >= 200
если
n >= 20000/(1 - c)
и мы можем взять c = 1/2 и n0 = 40000.