educative.io

Wrong time complexity?

Courses
,
#1

Hi all

Given that dequeue function takes O(n) shouldn’t the overall time complexity of this exercise be O(n^2) ?

Here is my solution:

def reverseK(queue, k):
    if queue.is_empty() or k>queue.size() or k<0:
        return None
    result = MyQueue()
    temp_stack = MyStack()
    while queue.size()>k:
        temp_stack.push(queue.dequeue())
    while not temp_stack.is_empty():
        result.enqueue(temp_stack.pop())
    while not queue.is_empty():
        result.enqueue(queue.dequeue())
    return result
#2

No the complexity is O(n) as the loop iterate on n elements.

#3

But the function dequeue() is defined as follow:

  def dequeue(self):
        if self.is_empty():
            return None
        front = self.front()
        self.queue_list.remove(self.front())
        self.queue_size -= 1
        return front

And the expression self.queue_list.remove(self.front()) will take O(n) for every time it is called which is n. Thats why I think it is O(n^2)

#4

No, it doesn’t take O(n) as front doesn’t iterate over n elements it just return first element and then we remove that element.

#5

I am talking about the remove() function not the front(), the remove is the one that takes O(n)

#6

The remove function will remove the first element so it will not take O(n)

#7

How queue_list is defined? Is it a normal python list? If yes, then correct each remove will cost it O(n).

#8

It’s O(1) to pop the last element off a list in Python. It’s O(n) to remove an arbitrary element.

If you want to be able to pop either the first or last element, you can use collections.deque() from the stdlib which has O(1) popleft and pop methods. A deque is implemented as a doubly linked list under the hood.

So it’s possible to remove from the front or back in O(1) time.