Чтобы доказать, что 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).