По всем важным параметрам берут запас от опасного, т.к. все параметры, обычно, одновременно не могут быть близкими к опасным, то получаем оценку снизу.

А если взять все параметры опасными, т.е. когда случаются все факторы одновременно (это очень редко м.б.), то получаем оценку сверху.

Наверное и к алгоритмам это подходит :)

Говорят

Кто говорит?

что оценка в худшем случае никак не может быть О()

Может, в том смысле, в каком определено «большое О», т.е. существует такая константа, что для всех наборов входных данных параметр «большого О» помноженный на эту константу будет больше всех значений какой-то функции. Итого, асимптотически хуже этой оценки сложность алгоритка быть не может, так как это уже завышенное худшее.

Другое дело, что это неточная оценка и, если хочется выполнять более детальное сравнение, желательны оценки с асимптотической эквивалентностью с парой старших членов. В таком случае «большое О» можно рассматривать как гарантию производительности для худшего случая.

Оценки О(g(N) не связаны напрямую с оценкой худшего случая. Как пример — оценка средней скорости quick sort, O(N log N) против оценки худшего случая, O(N^2). Обе выражаются через O(g(N)).

И кстати, совершенно правомерно утверждать, что оценка скорости сортировки пузырьком O(N^3), O(N^4) или O(N^5 * log N), ведь N^3, N^4 и (N^5 * log N) растут быстрее, чем N^2.

Что имеют в виду, когда говорят «оценка сложности в худшем случае» оценку сверху или оценку снизу?

Сбоку!

Так говорят вот тут http://shad.yandex.ru/lectures/algorithms_1.xml на 45ой минуте.

i-rinat выше дело говорит, а лектор кажется имел в виду аппроксимацию для конкретного случая, и там «о» или омега не распространяются на весь алгоритм, а только на тот конкретный случай. Вероятно, имелось в виду, что как бы мы не делали всё равно минимум n операций будет, так что оценка снизу там имеет смысл. Но это не оценка алгоритма, а случая, т.е. как бы «оценка операций снизу для худшего случая».

ПОчти Оффтоп

Вся беда в том, что при неограниченом вычислительном ресурсе можно вычислить все простые числа приблизительно за 4 такта идеального процессора