Включение квадратичной c функции в обозначение Big O

Question

Мы видели, что обозначение Big O обеспечивает строгую верхнюю границу для f (n). Это означает, что функция f (n) может работать лучше, но не хуже указанного значения.

Примеры функций в O (n3) включают: n2.9, n3, n3 + n, 540n3 + 10

Примеры функций, не входящих в O (n3): n3.2, n2, n2 + n, 540n + 10, 2n

Это из книги @Data Structures Using C ", Reema Thareja

Итак, вопрос в том, почему n ^ 2 отсутствует в n ^ 3, так как оно меньше и, следовательно, ниже верхней границы n ^ 3? В то же время n ^ 2.9 включено.

Answer 1

Это опечатка или какая-то другая ошибка. Все именованные функции находятся в O (n ^ 3), кроме n ^ 3.2.

В примере 2.1 из той же книги даже показано, что 4n ^ 2 находится в O (n ^ 3).