Википедия пишет что сложность сортировки вставками О(n2) (квадрат) в худшем случае. Дан худший случай - массив по убыванию: 321, нам нужен по возрастанию 123. Если учитывать только перестановки, то получаем:
321
2 вынул
3 сдвинул
2 вставил
231
1 вынул
3 сдвинул
2 сдвинул
1 вставил
Получили 123. Но действий произошло только 7, а должно быть 9 (3 в квадрате). Вроде ещё сравнения нужно учитывать. Добавим сравнения:
321
сравнить 2 и 3, 2 меньше - двигаем
2 вынул
3 сдвинул
2 вставил
231
сравнить 2 и 3, 2 меньше - ок не двигаем
сравнить 2 и 1, 1 меньше - двигаем
1 вынул
3 сдвинул
2 сдвинул
1 вставил
Действий стало уже 10, тогда сложность выходит О(n2 + 1). Я что-то не так считаю? Ошибка в википедии? или как посчитать правильно что бы было 9?
O(n^2)
иO(10000*n^2+1)
обозначают абсолютно одно и то же, то традиционно используется та запись, которая короче.