Так что я полностью потерялся в нотации большого о-о.
В моем задании я должен доказать или опровергнуть следующее, используя формальное определение.
3n³ - 7n² + 100n - 36 is in O(n³)
а также
n²/log(n) + 3n is in O(n²)
Может ли кто-нибудь помочь мне с этим и сказать мне, как доказать или опровергнуть.
f(n) ∈ O(g(n)) ⇔ lim supn → ∞ | f(n)/g(n) | < ∞
Поскольку ваши f(n) и g(n) являются полиномами, lim sup и lim совпадают. Итак, вы должны доказать:
limn → ∞ |(3n³ - 7n² + 100n - 36) / n³| < ∞
limn → ∞ |(3n³ - 7n² + 100n - 36) / n³| = limn → ∞ |n³(3 - 7/n + 100/n² - 36/n³) / n³| = limn → ∞ |3 - 7/n + 100/n² - 36/n³| = 3 < ∞
lim supn → ∞ |(n²/log(n) + 3n) / n²| < ∞
lim supn → ∞ |(n²/log(n) + 3n) / n²| = lim supn → ∞ |n²(1/log(n) + 3/n) / n²| = lim supn → ∞ |1/log(n) + 3/n| = 0 < ∞here you can also see that
n²/log(n) + 3n is also in o(n²).