Time complexity to add n values to an empty linked list so it is sorted?

Question

I have n unsorted values as input, and an empty linked list.

Those n values are added to the list in such a way that at the end the list is sorted.

What is the time complexity of the most efficient algorithm for this, in the worst case?

• Corentin Pane: What do you mean the worst? Once you have a solution, you can always do worse:)
• Shivansh Kumar: @CorentinPane time complexity in the worst case.
• Corentin Pane: Time complexity in the worst case depends on the actual algorithm you pick. Worst case complexity of the quick sort is O(n^2) for example, but I can come up with a silly algorithm working in O(n^18) as well. Do you mean "what is the best worst case time complexity I can hope for" maybe?

Answer 1

Usually a linked list is only accessed via its head; there is no random access to any node. This excludes any use of binary search.

So whenever a new value needs to be added to a linked list, the starting point is always the head of the list. The only way to proceed is to follow the next pointer to the next node in the list until a good insertion point is found, where the new node can be inserted.

In pseudo code:

insert_value_in_list(head, value):
 # create a node for the value
 node = new Node(value)
 # find out where it should be injected in the list
 prev = NIL
 node = head
 while node is not NIL and node.value < value:
 prev = node
 node = node.next
 # if there is a node that should precede...
 if prev is not NIL:
 node.next = prev.next
 prev.next = node
 else: # if there is no node that should precede, then make it the new head
 node.next = head
 head = node
 return head

The loop in this algorithm can take n iterations, where n is the current length of the list. This worst case happens when the inserted value is greater than all values that are already in the list.

So when inserting n values like that, the number of iterations of that loop can be in the worst case:

0 + 1 + 2 + 3 + 4 + 5 + ... + n-1

This is equal to (n-1)n/2, which is O(n2). The worst case happens when the inserted values are inserted in their sorted order.

All other parts of the insertion-algorithm run in constant time, so the time complexity in the worst case is (On2).

Note that the best case happens when the input is the reverse of the sorted order. In that case all values can be prepended to the list, and such a prepend-operation runs in constant time. Then the overall time complexity is O(n) -- best case.