Question

Consider implementing a Priority Queue (PrQUE) with a normal Linked Cell List. What is the worst case time complexity of the "FRONT" operation for a PrQUE with N items in it? (remember, "front" gives the highest priority element).

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

Answer 1

The worst-case time complexity of the 'FRONT' operation in a Priority Queue implemented using a normal linked list is O(N), since it may require traversing the entire list.

Step-by-step explanation:

If a Priority Queue (PrQUE) is implemented using a normal linked list, the worst-case time complexity of the FRONT operation, which retrieves the highest priority element, is O(N). In a typical unsorted linked list implementation, you would have to traverse the entire list to find the element with the highest priority, since elements are not in a specific order that reflects their priorities.