title: Is a.insert(0,x) an o(n) function? Is a.append an O(1) function? Python
body: <p>I am trying to move even numbers in an array to the front and odd numbers to the back of the array. The problem asks to do this in a Linear Algorithm and do this In Place.</p>
  
  <p>I came up with this:</p>
  
  <pre><code> def sort(a):
      for i in range(0,len(a)-1):
          if a[i]%2==0:
              a.insert(0,a.pop(i))
      return a
  </code></pre>
  
  <p>The issue is that, someone told me that technically, a.insert is an o(n) function so technically this would be considered a non-linear algorithm (when including the <code>for i in range</code> part of the function). Since the forum that asked this question is a couple months old, I couldn't ask for an explanation.</p>
  
  <p>Basically I believe he said "Technically" because since this inserts it at the front, it does not check another N number of elements in the array, therefore making it run for practical purposes at O(n) and not O(n^2). Is this a correct assessment?</p>
  
  <p>Also, someone on the forum used <code>a.append</code> to modify the above and changed it to look for odd numbers. No one replied so I was wondering, is a.append not an o(n) function since it moves it to the end? Is it o(1)?</p>
  
  <p>Thanks for explanations and clarifications!</p>