О-нотация игнорирует константы.
Это значит, что О-нотация не учитывает никакие числа, кроме показателей степени, — все остальные просто исключаются из выражения.
Поэтому в нашем случае, несмотря на то что алгоритм выполняет N 2/2 шагов, мы отбрасываем часть «/ 2» и выражаем эффективность алгоритма как O(N 2).
Прикладные структуры данных и алгоритмы. Прокачиваем навыки
·
Джей Венгроу
