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

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))