Для формального определения нижней и верхней границ времени выполнения алгоритма вводятся понятия О-большого (O-notation) и омега-большого (Ω-notation). О-большое (O-notation) используется для выражения верхней границы времени выполнения алгоритма. Формально, говорят, что функция g(n) принадлежит O(f(n)), если существуют положительные константы c и n0 такие, что для всех n > n0 выполняется неравенство 0 ≤ g(n) ≤ c * f(n). То есть, g(n) не превышает f(n) с точностью до константы. Омега-большое (Ω-notation) используется для выражения нижней границы времени выполнения алгоритма. Формально, говорят, что функция g(n) принадлежит Ω(f(n)), если существуют положительные константы c и n0 такие, что для всех n > n0 выполняется неравенство 0 ≤ c * f(n) ≤ g(n). То есть, g(n) не укладывается в f(n) с точностью до константы. Теперь мы можем определить формальный способ определения нижней и верхней границ времени выполнения алгоритма, используя понятия О-большого и омега-большого. Формально, говорят, что функция g(n) принадлежит классу θ(f(n)) тогда и только тогда, когда g(n) принадлежит и классу O(f(n)), и классу Ω(f(n)) для всех n > n0. Обратите внимание, что для класса θ(g(n)) введено ограничение на асимптотическое поведение функции g(n) не только сверху (через О-большое), но и снизу (через омега-большое). Это позволяет более точно описывать границы времени выполнения алгоритма. Однако стоит отметить, что не все функции можно описать с помощью класса θ(g(n)). Некоторые функции могут иметь только верхнюю (О-большое) или только нижнюю (омега-большое) границу. Например, для функции g(n) = n^2 + n принадлежность классу θ(n^2) можно описать только через О-большое, так как для омега-большого неравенство выполняться не будет при n=1.