What is the complexity of inserting into sorted link list in big-O notation?

Question

What is the complexity of inserting into sorted link list in big-O notation? Let say I have 5 elements and what is the complexity to insert all of them.

Thank you very much

Answer 1

Think about what a single insertion into a sorted link list means. You have a new element that has to go somewhere in the list.

1) You have to find the right place in the list. This is a linear search. O(n)

2) Insertion is easy: create new node, fix pointers to the previous and next nodes. O(1)

In this case, the O(n) outweighs the O(1) so it's O(n).

The number of elements doesn't really apply to big-O, since it's all based on orders of magnitude.

Answer 2

First, I'd recommend reading the Wikipedia article on Linked Lists, especially the (small) part about speeding up search.

Now, to answer your question, an insertion into a linked list takes O(1) time if you already know where you want to insert it. Since we're talking about a Sorted Linked List, and you're inserting without knowing where an element is supposed to go, it will take you O(n) time (since you have to search the whole list to find the place the element goes). Notice that actually adding the element is O(1), like I said above.

Notice that this is not a very effective search, since searching a sorted array, for example, takes O(lg(n)) time (using a Binary Search). Unfortunately, with an array, after finding the element, the insertion itself is not O(1) (it's usually O(n)), which means that using an array doesn't speed you up overall, even though the search is faster.