Question

Consider implementing a PrQUE with a BST that somehow guarantees average performance on all operations (not worst case). What is the worst case time complexity of the "FRONT" operation 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 "FRONT" operation in a BST-based PrQUE is O(N), assuming a degenerated tree where each node has only one child.

The "FRONT" operation on a priority queue (PrQUE) implemented using a Binary Search Tree (BST) that guarantees average performance involves finding the minimum element, which in a balanced BST would usually be an O(log N) operation. However, since we are considering the worst case time complexity, the BST might be degenerated into a linked list-like structure where every node has only one child.

This would result in the worst case time complexity being O(N) for the "FRONT" operation, because you would have to traverse from the root to the most left node (the minimum in a BST), which takes linear time relative to the number of items.

Therefore, the worst case time complexity for the "FRONT" operation in a BST-based PrQUE with N items is O(N).