Как может время работы алгоритма не изменятся при переходе к более скоростному алгоритму ?

Тут говорится о том, что соотношение между количеством выполняемой работы и затраченным временем по прежнему остаётся, и даже рассчитывается по одинаковой формуле, только с разными коэффициентами, но в новой версии эти коэффициенты лучше, соответственно лучше и всё затраченное на работу время. И это сбивает с толку, ведь, упоминается то, что казалось бы, и так очевидно. Но это немного не так... дело в том, что существуют алгоритмы, при которых разное по обьёму количество работы, может выполнятся за одинаковое количество времени, например в яве - существуют коллекции, скорость поиска в которых не зависит от количества элементов, примеров из других языков - не знаю, такие алгоритмы редкость и для новичка - совсем не очевидны. Автор книги, как бы намекнул: "в нашем алгоритме есть зависимость времени от количества работы, но в принципе этой зависимости может и не быть".

Это предложение явно не очень дружелюбное по отношению к новичкам в программировании, особенно после перевода на русский, но, зато автор всё изложил максимально технически-грамотно. :)

Так ведь O - это не время, а вычислительная сложность: требуемое кол-во АБСТРАКТНЫХ (т. е. не имеющих отношения к работе реального процессора) атомарных операций сравнения и пересылки данных.

O(N**2) означает, что зависимость кол-ва операций, выполняемых алгоритмом, от кол-ва входных данных - квадратичная функция. Но ничего не говорит о коэф-тах этой квадратичной функции. Потому это может быть и x**2, и 16*x**2 + 32*x

Например, HeapSort и QuickSort - оба по вычислительной сложности O(N*log(N)). Но HeapSort в среднем в 1.4 раза медленнее.