title: Is insertion time complexity of sorted-list implementation of priority queue O(n)?
body: <p>From <a href="http://en.wikipedia.org/wiki/Priority_queue" rel="nofollow noreferrer">wikipedia</a>:</p>
  
  <blockquote>
    <p>Sorted list implementation: Like a
    checkout line at the supermarket, but
    where important people get to "cut" in
    front of less important people. (<strong>O(n)</strong>
    insertion time, O(1) get-next time,
    O(n*log(n)) to build)</p>
  </blockquote>
  
  <p>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.</p>
  
  <p>So am I wrong or wikipedia is incorrect?</p>
  
  <p><strong>Update</strong>:
  According to the strict definition of list from TAOCP:</p>
  
  <blockquote>
    <p>A linear list is a sequence of n >=0
    nodes X<a href="http://en.wikipedia.org/wiki/Priority_queue" rel="nofollow noreferrer">1</a>, X[2], ... , X[n] whose
    essential structural properities
    involve only the relative positions
    between items as they appear in a
    line.</p>
  </blockquote>
  
  <p>I assume the <strong>list</strong> wikipedia refer is not <strong>linked-list</strong>,and it could be <strong>array</strong>.</p>
  
  <p>thanks. </p>