В Algorithmica хорошо разобрали, почему классическая оценка сложности всё хуже отражает реальную производительность на современном железе. Раньше модель была довольно логичной: процессор выполняет инструкции почти последовательно, у каждой есть своя стоимость, а значит можно примерно оценить время работы алгоритма количеством операций. Потом всё упростили до асимптотики. Например, вместо точного количества операций в умножении матриц мы просто говорим O(n³) и игнорируем константы. Для сравнения алгоритмов на больших данных это удобно...