complexity of the insertion sort using Doubly Linked List?

Question

Insertion sort requires insertion of an element in sorted order by shifting the elements of an already sorted list while implemented through array. If instead of using arrays, we use doubly linked-list, what would be the time complexity?

Time Complexity Comes out to be O(n^2)? Why? If we consider insertion for n elements then it will be log(1) + log(2) + log(3) + ..... + log(n) - n times for n elements hence complexity should be O(nlogn)

• amit: What makes you think it's log(1) + log(2) + ... + log(n) and not 1 + 2 + ... + n ? Please add more details in the questions, so you will get better more informative answers - which will be more likely to explain where your mistake is.
• Luv: for insertion using insertion sort if we use doubly linked list then insertion of an element takes log(k) time where k is the number of already sorted elements

Answer 1

Insertion into a linked list takes time O(n), not O(lg n), because you have to navigate the link structure to find the insertion point.