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.

The way it's currently written, it will return after the first `pop(0)` which means the function is O(1). — Brent Washburne, Nov 03 '15 at 01:31
`pop()` is O(1): https://wiki.python.org/moin/TimeComplexity — Brent Washburne, Nov 03 '15 at 01:32
If you are going to pop from the left, use a `collections.deque` because popleft for those is O(1). https://wiki.python.org/moin/TimeComplexity — RobertB, Nov 03 '15 at 01:32
@BrentWashburne Ah thanks for spotting that, I had the indent of the return wrong. EDITED thanks — Jacklin213, Nov 03 '15 at 01:35
`collections.deque` are optimized for adding / removing from both ends. Per the docs, pop(0) on a list is O(N). https://docs.python.org/2/library/collections.html#collections.deque — RobertB, Nov 03 '15 at 01:36

Martijn Pieters · Accepted Answer · 2015-11-03T01:36:59.843

4

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

edited Nov 03 '15 at 01:36

answered Nov 03 '15 at 01:32

Martijn Pieters

1,048,767
296
4,058
3,343

@MartijnPieters you have to multiply the complexity of the while and the pop – spirographer Nov 03 '15 at 01:33
If list.pop(0) is O(N) and you have it in a while loop, that makes it O(N^2) – RobertB Nov 03 '15 at 01:34
@spirographer: The loop only ever takes 1 step, because `return` exits it. – Martijn Pieters Nov 03 '15 at 01:34
@RobertB: no, because the while loop exits early. – Martijn Pieters Nov 03 '15 at 01:34
@MartijnPieters Sorry I had indented the return wrong. What would it be now? – Jacklin213 Nov 03 '15 at 01:36
1

@Jacklin213: ah, that was not helpful. – Martijn Pieters Nov 03 '15 at 01:37
Might be worth noting in this answer that using a collections.deque instead of a list would change this to O(N) since the deque.popleft() is O(1). – RobertB Nov 03 '15 at 01:41
@RobertB: feels a little too much out of scope here. It's fine in a comment on the question. – Martijn Pieters Nov 03 '15 at 01:44
@MartijnPieters, I guess, but in the original question the data type was not specified, so I felt it was ambiguous. If you pass a `collections.deque` into the function `clear_list` as written, it would be O(N). If you pass a list into that exact same function, it is O(N^2). So the Omega of the function is ambigous. Thank you duck-typing. – RobertB Nov 03 '15 at 01:46

score 3 · Answer 2 · edited May 23 '17 at 11:51

3

It's going to be O(n^2) because in the while loop you have to go through all n elements, and in the pop you have to shift all of the elements that follow the first element.

Here's a link to a related answer: What is the time complexity of popping elements from list in Python?

edited May 23 '17 at 11:51

Community

1
1

answered Nov 03 '15 at 01:32

spirographer

630
4
18

@MartijnPieters the return is not in the loop – spirographer Nov 03 '15 at 01:37
That was a mistake from OP. This answer is correct. – RobertB Nov 03 '15 at 01:37

score 3 · Answer 3 · edited Nov 03 '15 at 04:24

3

I just benchmarked this for you (EDIT: I assumed the return was misplaced since otherwise why do I even)

from time import time
def check(size):
    a = range(size)
    start = time()
    clear_list(a)
    return time() - start
check(40000) # About .4 seconds on my computer
check(80000) # About 1.6 seconds on my computer

Clearly O(n²)

edited Nov 03 '15 at 04:24

displayName

13,888
8
60
75

answered Nov 03 '15 at 01:35

Alec

583
3
21

Thanks for the benchmark :) Helped me visualize it :) – Jacklin213 Nov 03 '15 at 01:40

Big-O of a while loop

3 Answers3