CODEWITHSUNDEEP
sortinglinked-listcomplexity-theoryinsertion-sort
Luv
Luv

Reputation: 5451

complexity of the insertion sort using Doubly Linked List?

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)

Upvotes: 0

Views: 2171

Answers (1)

Fred Foo
Fred Foo

Reputation: 363547

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.

Upvotes: 2

Related Questions