0

I'm currently doing some work around Big-O complexity and calculating the complexity of algorithms.

I seem to be struggling to work out the steps to calculate the complexity and was looking for some help to tackle this.

The function:

index = 0
    while index < len(self.items):
        if self.items[index] == item:
            self.items.pop(index)
        else:
            index += 1

The actual challenge is to rewrite this function so that is has O(n) worst case complexity.

My problem with this is, as far as I thought, assignment statements and if statements have a complexity of O(1) whereas the while loop has a complexity of (n) and in the worst case any statements within the while loop could execute n times. So i work this out as 1 + n + 1 = 2 + n = O(n)

I figure I must be working this out incorrectly as there'd be no point in rewriting the function otherwise.

Any help with this is greatly appreciated.

Adam Roberts
  • 562
  • 1
  • 5
  • 20
  • Its depend on the data structure of your input (items). The pop operation's time complexity. Please tell us the data structure type of the `self.items`. If its a list look at the complexity of the pop operation on a list simple. – BetaDev Apr 14 '19 at 17:21

3 Answers3

2

If self.items is a list, the pop operation has complexity "k" where k is the index, so the only way this is not O(N) is because of the pop operation.
Probably the exercise is done in order for you to use some other method of iterating and removing from the list.

To make it O(N) you can do:

self.items = [x for x in self.items if x == item]
Miguel
  • 1,295
  • 12
  • 25
  • So in the worst case, as the pop operation is within the while loop, this would mean the algorithm has complexity O(n^2)? – Adam Roberts Apr 14 '19 at 17:28
  • More precisely O(N*(N+1) /2), since in the worst case it will do 1 iteration for index1, 2 for index = 2, 3 for index = 3 and so on... The sum of the natural numbers of 1 to N is the one mentioned above. But yes general case is O(n^2) – Miguel Apr 14 '19 at 17:31
  • 1
    I'm very limited with the operations I'm allowed to use so technically I can't use that solution, however this is given me what I needed and I think I can re-write it within the guidelines set now, thanks! – Adam Roberts Apr 14 '19 at 17:38
  • `O(n*(n+1)/2)` *is* `O(n^2)`; big-oh notation renders the difference between `n^2` and `1/2n^2 + n/2` meaningless. – chepner Apr 14 '19 at 22:37
1

If you are using Python's built in list data structure the pop() operation is not constant in the worst case and is O(N). So your overall complexity is O(N^2). You will need to use some other data structure like linked list if you cannot use auxiliary space.

xashru
  • 3,400
  • 2
  • 17
  • 30
1

With no arguments to pop its O(1)

With an argument to pop:

  • Average time Complexity O(k) (k represents the number passed in as an argument for pop
  • Amortized worst case time complexity O(k)
  • Worst case time complexity O(n)

Time Complexity - Python Wiki

So to make your code effective, allow user to pop from the end of the list:

for example:

def pop():
    list.pop(-1)

Reference

Since you are passing index to self.items.pop(index), Its NOT O(1).

BetaDev
  • 4,516
  • 3
  • 21
  • 47
  • 1
    Strictly speaking, not just the default `pop()` is O(1); *any* argument that is constant with respect to `n` results in an O(1) operation. `items.pop(-1000)` is O(1), because you have to shift at most 1000 items as `n` increases. `items.pop(1000)` is O(n), because as `n` grows, you have to shift `n-1000` items. – chepner Apr 14 '19 at 22:40