Is A.insert(0,x) An O(n) Function? Is A.append An O(1) Function? Python

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. I came u

Solution 1:

insert at the 0th index of a list requires shifting every other element along which makes it an O(N) operation. However, if you use a deque this operation is O(1).

append is an amortized O(1) operation since it simply requires adding the item on to the end of the list and no shifting is done. Sometimes the list needs to grow so it is not always an O(1) operation.

Solution 2:

That is correct - insertion at the front of a Python standard list is O(n). Python lists are implemented as arrays, and thus inserting something at the front of the list requires shifting the entire contents over one spot. Appending, on the other hand, does not require any shifting, and thus is amortized O(1).

Note, however, that a.pop(i) is also an O(n) operation, because it requires shifting everything after the popped item over one spot. Thus, simply modifying your code to use append() instead of insert() would still not result in a linear algorithm.

A linear-time algorithm wouldn't use pop() but instead would do something like swap elements around so that the rest of the list doesn't have to be modified. For example, consider this:

def even_to_front(a_list):
    next_even = 0
    for idx in xrange(len(a_list)):
        if not a_list[idx] % 2:
            # a_list[idx] is even, so swap it towards the front
            a_list[idx], a_list[next_even] = a_list[next_even], a_list[idx]
            next_even += 1

Solution 3:

Here's how it can be done without append/insert or dequeue

def sort(L):
    i, j = 0, len(L)-1
    while i<j:
        # point i to the next odd number from the start
        while i<j and not L[i]%2: i+=1
        # point j to the next even number from the end
        while i<j and L[j]%2: j-=1
        L[i],L[j] = L[j],L[i]    

Solution 4:

Check this table of complexity

• Insert - O(n)
• Append - O(1) (lists are over allocated)