Асимптотические нижние границы

Это определение работает точно так же, как O(), не считая того, что функ- ция T(n) ограничивается снизу, а не сверху. Например, возвращаясь к функции T(n) = рn² + qn + r, гдер, q и r — положительные константы, будем утверждать, что T(n) = Ω(n²). Если при установлении верхней границы приходилось «раздувать» функцию T(n) до тех пор, пока она не начинала выглядеть как произведение n² на константу, на этот раз нужно сделать обратное: «подрезать» T(n), пока она не начнет выглядеть как произведение n² на константу. Сделать это несложно; для всех n > 0

T(n) = рn² + qn + r > рn²,

что соответствует требованию определения Ω(·) с е = р > 0.

Для нижних границ существует то же понятие «точности» и «слабости», что и для верхних. Например, будет правильно утверждать, что функция T(n) = рn² + qn + r имеет Ω(n), так как T(n) >рn² >рn.