What time complexity is this function?

Question

I have been given a small and simple function to refactor into a function that is O(n) complexity. However, i believe the function given already is, unless I am missing something?

Basically the idea of the function is simply to iterate over a list and remove the target item.

for i in self.items:
        if i == item:
            self.items.pop(i)

I know the for loop gives this a O(n) complexity but does the additional if statement add to the complexity? I didn't think it did in the worst-case for this simple piece of code.

If it does, is there a way this can be re-written to be O(n)?

I cannot think of another way to iterate over a list and remove an item without using a For loop and then using an if statement to do the comparison?

PS. self.items is a list of words

`.pop(i)` is O(N), so it is O(N^2) overall. Generally, you just *make a new list filtering as you go*, which will be O(N), so `self.items = [i for i in self.items if i != item]` (or the equivalent for-loop would be just as good). Your approach *also* happens to incorrect, as it may skip items to remove (because you are mutating the list while iterating over it) — juanpa.arrivillaga, Mar 06 '19 at 19:49
Be warry that except for being O(n^2) this code has other issues, such as changing the size of the list while iterating it — DeepSpace, Mar 06 '19 at 19:51
I don't understand how this code can work.`pop` takes an index, but you're giving it a list element. — , Mar 06 '19 at 19:54

blhsing · Answer 1 · 2019-03-06T19:55:06.417

2

The list.pop method has an average and worst time complexity of O(n), so compounded with the loop, it makes the code O(n^2) in time complexity.

And as @juanpa.arrivillaga has already pointed out in the comments, you can use a list comprehension instead to filter out items of a specific value in O(n) time complexity:

self.items = [i for i in self.items if i != item]

edited Mar 06 '19 at 19:55

answered Mar 06 '19 at 19:49

blhsing

91,368
6
71
106

The worst case occurs if `item` occurs *n/2* times, say, and they all reside in the bottom half of the list. – jxh Mar 06 '19 at 20:00

score 1 · Answer 2 · answered Mar 06 '19 at 19:51

for i in self.items: # grows with the cardinal n of self.items
    if i == item:
        self.items.pop(i) # grows with the cardinal n of self.items

So you have a complexity of O(n²).

The list method remove(item) in python though is of complexity O(n), so you'd prefer use it.

self.items.remove(item)

score 0 · Answer 3 · answered Mar 06 '19 at 19:54

0

Your current solution has the time complexity of O(n^2).

For an O(n) solution you can just use for example an list comprehension to filter all the non wanted elements from the list:

self.items = [i for i in self.items if i != item]

answered Mar 06 '19 at 19:54

ruohola

21,987
6
62
97

1

Furthermore, this code actually works, because other codes change the size of the array while iterating. – Benoît P Mar 06 '19 at 19:56

Daniel Lenz · Answer 4 · 2019-03-07T01:19:32.513

First, you'd have to slightly adjust your code. The argument given to pop() is currently an item, where it should be an index (use remove() to remove the first occurrence of an item).

for i, item in enumerate(self.items):
        if item == target:
            self.items.pop(i)

The complexity depends on how often item matches the element in your list.

Using n=len(items) and k for the number of matches, the complexity is O(n, k) = O(n) + k O(n). The first term comes from the fact that we iterate through the entire list, the second one corresponds to the individual .pop(i) operations.

The total complexity for k=1 is thus simply O(n), and could go up to O(n*n) for k=n.

Note that the complexity for .pop(i) is O(n-i). Hence, popping the first and last element is O(n) and O(1), respectively.

Lastly, I'd generally recommend not to add/remove items to an object that you're currently iterating over.

What time complexity is this function?

4 Answers4