Чтобы доказать, что T(n) = n^3 + 20*n + 1
равно O(n^4)
, просто примените определение big-O.
Нам нужно показать, что существуют положительная постоянная M > 0
и число N
, такие что
|T(n) / n^4| < M
для всех n > N
Теперь возьмите M = 3
и N = 3
.Тогда для любого n > N
имеем |T(n) / n^4| = |(n^3 + 20*n + 1) / n^4| = |1 / n + 20 / n^3 + 1 / n^4| < |1/3 + 20/27 + 1/81| < |1 + 1 + 1| = 3 = M
.КЭД
Верно, что наиболее значимый термин в T(n)
при n, равный бесконечности, равен n^3
, но это не отрицает того факта, что T(n)
равен O(n^4)
.Используя аналогичный аргумент, можно показать, что T(n)
равно O(n^3)
(на самом деле T(n)
- это биг-тета n^3
, которое сильнее, чем big-O n^3
).