Можем ли мы оценить Big Omega так же, как мы делаем с Big O?

Question

Я продолжаю читать, как легко оценить Большой О: отбросить наименее доминирующие термины и константы.Мой вопрос: можем ли мы сделать то же самое для Big Omega?

Я знаю, что входная зависимость не имеет ничего общего с асимптотическим анализом: мы можем иметь верхний (Big O) и нижний (Big Omega) в лучшем, среднеми анализ наихудшего случая.Но я запутался в том, как я могу быстро оценить Большую Омегу моего алгоритма, в худшем случае, например.

Если бы вы могли привести примеры, чтобы прояснить мою путаницу, я был бы очень признателен.

Answer 1

Всего два примера должны вас просветить.

n² + n - это O(n²) (это также O(n³)).

n² + n - это Ω(n²) (это также Ω(n)).

Вы рассматриваете доминирующий термин.

n + (n cos n)² равен O(n²) и Ω(n).

Верхняя и нижняя границы.