Big-O of a while loop

Question

I was wondering what the Big-O of this code snippet is

def clear_list(my_list):
    while len(my_list) > 0:
        my_list.pop(0)
    return my_list

Would it be O(n^2) or O(n) because the while loop is O(n) or O(1) and pop(0) is O(n) as well. I don't think the while loop is O(log n) since no value that is being compared in the while loop is cut in half.

Answer 1

It is O(N^2):

• The while loop takes N steps, until all elements have been removed.

• list.pop(0) is O(N); all elements in the list following have to shift up one step. That the list is shortened each step still gives you an average of 1/2 N steps over the whole process, where the 1/2 can be ignored (it doesn't matter when viewed asymptotically).