Здравствуйте, samius, Вы писали:

S>То есть, асимптотика не предназначена для описывания нижних оценок на малых n.

Речь не только про малые n.

S>Причем Кнут — не понятно.

При том, что Кнут не учитывал, как алгоритмы выполняются на современном железе, такая теория в вакууме. Знать надо, но каждый раз надо думать, а слепо верить в О.

S>Он не утверждает обратного.

Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска одинакова — логарифм. Значит ли это, что они одинаково эффективны? Нет, ведь дерево может быть размазано по памяти из-за этого возникнут постоянные промахи в кеш и упорядоченный массив окажется в разы эффективней. Рассматривается это у Кнута? Нет, вот о том и речь.