Question

Consider a QUEUE implemented by linked list, and containing N elements. If we manage to implement the ENQUE operation in O(1) time worst case, what is the "best" worst case time complexity we can get for the DEQUE operation?

a. O(1)
b. O(log N)
c. O(N)
d. O(N²)

Answer 1

If the ENQUE operation is done in O(1) time for a QUEUE implemented by linked list, the best worst case time complexity for the DEQUE operation is also O(1).

Step-by-step explanation:

If the ENQUE operation in a QUEUE implemented by linked list can be done in O(1) time worst case, the best worst case time complexity we can achieve for the DEQUE operation is also O(1). This is because if the ENQUE operation is O(1), it means that adding an element to the end of the linked list takes constant time. In this case, the DEQUE operation to remove the first element from the linked list can also be performed in constant time by updating the reference to the first element.