Is insertion time complexity of sorted-list implementation of priority queue O(n)?

Question

From wikipedia:

Sorted list implementation: Like a checkout line at the supermarket, but where important people get to "cut" in front of less important people. (O(n) insertion time, O(1) get-next time, O(n*log(n)) to build)

I think if searching the insert position with binary search algorithm,the insertion time complexity should be O(log(n)).Here I treat the arrival order of jobs as a factor of priority.

So am I wrong or wikipedia is incorrect?

Update: According to the strict definition of list from TAOCP:

A linear list is a sequence of n >=0 nodes X1, X[2], ... , X[n] whose essential structural properities involve only the relative positions between items as they appear in a line.

I assume the list wikipedia refer is not linked-list,and it could be array.

thanks.

Answer 1

It seems that in your quote, Wikipedia is referring to a priority queue backed by a sorted list, rather than a heap. To insert an item into a sorted list requires O(n) time (assuming that we are maintaining its sortedness).

Answer 2

Binary search is indeed O(log n) but binary search works on arrays - it works in this time because you can access any element in O(1).

However, in literature when you see the term list you should be thinking about linked lists. In a list therefore, you do not have O(1) access time, but rather you need to search for the position "by hand" - so inserting an element would take O(n).

Answer 3

The worst case insertion time in a sorted list is O(n). The worst case is inserting the highest item into the list. To do that you have to step through all the elements, then insert at the end. The reason you don't get to do a binary search is that only element that you can access in the list is the successor of your current element, i.e. no random access.

Answer 4

Wikipedia is correct. As others here have already stated, lists are not random-access, hence you need to visit each node between A and B before you get to B. That makes binary search useless as traversing the list is O(n), so you end up doing more work than if you just iterated over the list once. You could cache the start, middle and end nodes in a separate buffer and check those first. However, that would just have the same effect as using multiple lists. The skip-list data structure takes that idea one step further.

So use a random-access heap instead, or perhaps a skip-list: http://en.wikipedia.org/wiki/Skip_list depending on your needs.

Answer 5

if the it's linked list backed you can't do binary search so; finding the insertion point is O(n), actually inserting is O(1) as you just change the adjacent nodes, overall O(n).

if its array backed you can do a binary search so; finding the insertion point is O(log(n)), but inserting in an array is O(n) as you may have to shift all the elements of the array, overall O(n)

this is why you actually have tree/heap backed so all operations can be O(log(n))