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

Solution 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.

Solution 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.

Comments

[Tron]

but you are doing O(n) searches n times, that wouldn't make it O(N^2)?

[Nick Johnson]

@Tron: No, the number of insertions doesn't depend on the length of the list - it's O(mn).

[Steve Jessop]

I think the question is worded a little hazily, but now what I suspect he means is he's starting with an empty list, and inserting N elements. In which case, saying "let's say 5" is completely misleading, since if N isn't a variable, then complexity is not a relevant concept.

[Rob Parker]

If you want the search and insertion to both be faster, you probably want to use a b-tree (is that what it's called?) as the data structure. I believe in-order traversal is still O(n), but searches (eg. to find insersion point) are O(lg(n)) and I think single insersions are also O(lg(n)) or a slight variation of that (maybe it was O((lg(n))^2).

[ewanm89]

@NickJohnson Yes, it's O(mn) but isn't m = n-1 (given O is worst case), in which case it's O(n(n-1)), which is O(n^2 - n) which is not an order of magnitude better than O(n^2). Yes it is slight optimisation over linear insertion sort of arrays technically, but not enough to warrant giving it's own algorithm definition and complexity.

[ewanm89]

@RobParker if we are going to start to bring in complicated tree data structures (which have a big setup time), we might as well skip straight to heap sort with O(n.log(n))

[Nick Johnson]

@ewanm89 I think Steve Jessop describes what's probably going on here better than I can.

[Rob Parker]

@ewanm89, I'm not sure a heap sort is particularly any faster than sorting with a b-tree (maybe slightly), but "sorting" was not the goal. The goal (slightly expanding on the original question) was to minimize insertion time in a "list" maintained in sorted order. A b-tree (if I have the right term for it) is maintained in sorted order (if traversed the right way), is binary-searchable, and is efficient for insertion and deletion (slightly less than for a linked-list which is not efficiently searchable).