BigOh просто говорит, что скорость роста не может быть больше, чем постоянный коэффициент скорости роста конкретной функции, она не может показать, что такое скорость роста.
Обновление
Предположим, что f (n) = 2 * f (n-1) + 1 и f (1) = 1, означает, что f (n) = 2 n - 1, BigOh для этой функции может быть :
BigOh (f (n)) принадлежит {2 n , 2 n-100 , 2 2 * n , 2 2 n , ...}, но не принадлежит {2 n / 2 , n 2 , ....}
Как вы можете видеть, такие функции, как 2 2 n имеют очень очень высокую скорость роста, но показывают BigOh для 2 n .
Некоторые функции невероятны, и никто не находит их точную скорость, одно из лучших применений BigOh в таких ситуациях.
На самом деле, когда вы не можете определить & theta; Хорошо найти хорошего BigOh, честно говоря, моя функция (алгоритм) не медленнее, чем эта функция. Так что BigOh является ценным, но опять же может быть очень далеко от вашей функции растет скорость. BigOh хорош для рандомизированных алгоритмов и для детерминированных сложных функций.