Question

Consider implementing a PrQUE with a BST that somehow guarantees average case performance on all operations (not worst case). What is the worst case time complexity of "ENQ" on such a PrQUE with N items in it?

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

Answer 1

The worst-case time complexity for the 'ENQ' operation in a priority queue implemented with a BST, which guarantees average-case performance, is O(N). This occurs when the BST becomes unbalanced, resembling a list.

Step-by-step explanation:

The question asks about the worst-case time complexity of the 'ENQ' (enqueue) operation in a priority queue (PrQUE) that is implemented with a binary search tree (BST) designed to guarantee average-case performance. It's important to note that what is being sought is the worst-case scenario, not the average case. The worst-case time complexity for enqueuing an element in such a structure happens when the tree becomes unbalanced, resembling a linked list. In this scenario, the time complexity for inserting (enqueuing) would be O(N), as you would need to traverse the entire tree, which is effectively a list due to the imbalance. Therefore, the answer would be option (a) O(N).