Как понять обозначение Big O в данном примере

Question

Здесь указывает, что T (n) равно O (n ^ 4).Но я хочу знать, почему это не O (n ^ 3)?Он содержит n ^ 3, и если мы опускаем 20n и 1, это должно быть O (n ^ 3), а не O (n ^ 4).Почему это так?

Answer 1

Это в O (n ^ 3), но O (n ^ 4), O (n ^ 5) и т. Д. Является надмножеством O (n ^ 3), поэтому, если что-то находится в O (n ^ 3)тогда оно также может быть в O (n ^ 100).Лучший ответ и тот, который используется по соглашению, это наименьший большой O, к которому он принадлежит, то есть O (n ^ 3), но это не единственный.

Answer 2

Я думаю, что вы путаетесь между тета-нотацией и нотацией большого O.

Тета-нотация определяет приблизительную оценку времени выполнения алгоритма, тогда как нотация Big O определяет наихудшее время выполненияалгоритм.

Метод, который вы упомянули выше, используется для вычисления тэты, а не больших O. Большой O в вышеупомянутой проблеме может быть O (n ^ 4), O (n ^ 5), O (n^ 6) и так далее ... все правильные значения.Но для тэты только тэта (n ^ 3) верна.