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

Если можно показать, что время выполнения T(n) одновременно характеризуется O( f (n)) и Ω( f (n)), то возникает естественное ощущение, что найдена «правильная» граница: T(n) растет в точности как f (n) в пределах постоянного коэффициента. Например, к такому выводу можно прийти из того факта, что T(n) = pn2 + qn + r одновременно имеет O(n2) и Ω(n2).

Асимптотически точные границы для худшего времени выполнения полезны, поскольку они характеризуют быстродействие алгоритма в худшем случае с точно- стью до постоянного множителя. И, как следует из определения Θ(·), такие границы могут быть получены сокращением промежутка между верхней и нижней грани- цами.

Например, иногда приходится читать (отчасти неформально выраженные) утверждения вида «Показано, что в худшем случае время выполнения алгоритма имеет верхнюю границу O(n3), однако не существует известных примеров, для которых алгоритм выполняется за более чем Ω(n2) шагов». Такое утверждение можно считать неявным предложением поискать асимптотически точную границу для худшего времени выполнения алгоритма.

Иногда асимптотически точная граница может быть вычислена напрямую, как предел при стремлении n к бесконечности. Фактически если отношение функ- ций f (n) и g(n) сходится к положительной константе, когда n уходит в бесконеч- ность, то f (n) = Θ(g(n)).

Доказательство. Мы воспользуемся тем фактом, что предел существует и он положителен, чтобы показать, что f (n) = O(g(n)) и f (n) = Ω(g(n)), как того требует определение Ω(·).существует и равен некоторому числу c > 0. Тогда f (n) = Θ(g(n)). из определения предела следует, что существует некоторое значение n0, начиная с которого отношение всегда лежит в диапазоне между   и 2c. Таким образом, поскольку f (n) ≤ 2cg(n) для всех n ≥ n0, из чего следует, что f (n)=O(g(n)); а f (n) ≥  для всех n ≥ n0, из чего следует, что f (n) = Ω(g(n)).