Сложность вставки сортировки с использованием двусвязного списка?

Question

Вставка сортировки требует вставки элемента в отсортированном порядке путем смещения элементов уже отсортированного списка при реализации через массив. Если вместо использования массивов мы используем дважды связанный список, какова будет временная сложность?

Сложность времени выходит O(n^2)? Зачем? Если мы рассмотрим вставку для n элементов, то это будет log(1) + log(2) + log(3) + ..... + log(n) - n раз для n элементов, следовательно, сложность должна быть O(nlogn)

Answer 1

Вставка в связанный список занимает время O (n), а не O (lg n), потому что вам нужно перемещаться по структуре ссылок, чтобы найти точку вставки.