For a priority queue implemented using an ordered linked list, what is the…
2021
For a priority queue implemented using an ordered linked list, what is the worst-case time complexity of inserting a node at the position determined by its key?
Answer: D. O(n) — ConceptA priority queue may use different representations. In an ordered linked list, insertion must first locate the key-based position; the link change…
- A.
O(n log n)
- B.
O(log n)
- C.
O(n2)
- D.
O(n)
- E.
Question not attempted
Attempted by 509 students.
Show answer & explanation
Correct answer: D
Concept
A priority queue may use different representations. In an ordered linked list, insertion must first locate the key-based position; the link change itself is constant-time, but the search can span the list.
Application
Start at the head and compare the new key with successive nodes while preserving priority order.
In the worst case, the insertion point is at the end, so all n existing nodes are inspected.
After the position is found, updating the neighboring links takes O(1) time.
Cross-check
Ordered linked list: a linear search dominates the constant-time link update.
Binary heap: insertion instead follows one root-to-leaf path and takes O(log n).
Unordered list: insertion can be O(1), with the search cost deferred to removal.
Result
Therefore, insertion into the stated ordered linked-list priority queue has worst-case time complexity O(n).