Это особенность точности.Бывает, что обычно легче доказать, что алгоритм потребует, скажем, O(n) операций для завершения, чем доказать, что он будет не менее O(n) операций (кстати, в этом контексте операция означает элементарные вычисления, такие как логические и арифметические.)
Предоставляя нижнюю границу, вы также даете оценку лучший случай Сценарий, поскольку нотация big-O обеспечивает только верхнюю границу.
С практической точки зрения, это дает преимущество в том, что независимо от того, что любой алгоритм потребует так много (элементарный) шагов (или более).
Обратите также внимание, что также полезно иметь оценки среднего , худшего и лучшего случаи, потому что они проливают больше света на сложность алгоритма.
Существуют проблемы, присущая сложность которых известна, по крайней мере, некоторого порядка (имеется в виду математическаядоказательство факта).Таким образом, независимо от алгоритма, эти проблемы не могут быть решены с помощью определенного количества вычислений.Это также полезно, поскольку позволяет узнать, является ли данный алгоритм неоптимальным или соответствует присущей ему сложности проблемы.