CODEWITHSUNDEEP
pythontime-complexitybig-o
Adam Roberts
Adam Roberts

Reputation: 692

Calculating complexity of an algorithm (Big-O)

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.

Upvotes: 0

Views: 1351

Answers (3)

BetaDev
BetaDev

Reputation: 4684

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

Upvotes: 1

Miguel
Miguel

Reputation: 1355

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]

Upvotes: 2

xashru
xashru

Reputation: 3590

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.

Upvotes: 1

Related Questions