N items are stored in a sorted doubly linked list. For a delete operation, a…
2021
N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: Θ(N) delete, O(log N) insert, O(log N) find and Θ(N) decrease-key. What is the time complexity of all these operations put together?
Answer: C. O(N2) — Concept. Two rules decide this kind of question. First, the cost of a batch of operations is (how many times the operation runs) × (the cost of one run), and…
- A.
O(log2 N)
- B.
O(N)
- C.
O(N2)
- D.
Θ(N2 log N)
- E.
Question not attempted
Attempted by 509 students.
Show answer & explanation
Correct answer: C
Concept. Two rules decide this kind of question. First, the cost of a batch of operations is (how many times the operation runs) × (the cost of one run), and the cost of a whole sequence of batches is the sum of those batch costs, which the largest term dominates. Second, a linked list gives no random access: reaching or placing a node by position always costs a traversal proportional to the number of nodes, so keeping the list sorted does not enable binary search. A supplied pointer removes only the search step — with a pointer in hand, unlinking or relinking a node in a doubly linked list is O(1), because the node already knows both of its neighbours.
Application. Take the four batches in turn, using the count given in the stem and the per-operation cost that the data structure forces.
Θ(N) delete. A pointer to the record is supplied, so each delete only rewires the two neighbouring nodes: O(1) per delete. Batch cost = Θ(N) × O(1) = O(N).
O(log N) insert. No pointer is supplied, so each insert must walk the list to find where the new key belongs in sorted order: O(N) per insert. Batch cost = O(log N) × O(N) = O(N log N).
O(log N) find. A sorted linked list still has to be scanned sequentially, because there is no way to jump to a middle element: O(N) per find. Batch cost = O(log N) × O(N) = O(N log N).
Θ(N) decrease-key. The pointer makes the key change itself O(1), but a smaller key can break the sorted order, so the node must be unlinked and re-inserted at its new position — and locating that position is a traversal: O(N) per operation. Batch cost = Θ(N) × O(N) = O(N2).
Adding the batches. O(N) + O(N log N) + O(N log N) + O(N2) = O(N2), because N2 grows faster than N log N and than N, so the quadratic term swallows the rest. The four operation batches together therefore run in O(N2) time.
Cross-check.
Operation | Times performed | Cost of one run | Batch cost |
|---|---|---|---|
delete | Θ(N) | O(1) — pointer supplied | O(N) |
insert | O(log N) | O(N) — traversal to position | O(N log N) |
find | O(log N) | O(N) — sequential scan | O(N log N) |
decrease-key | Θ(N) | O(N) — reposition after key drop | O(N2) |
all four together | — | — | O(N2) |
Why the other bounds do not fit.
O(log2 N) would need every batch to avoid any step whose cost grows with N. Both insert and decrease-key need a traversal, so that is impossible on a linked list.
O(N) would need each of the Θ(N) decrease-key operations to cost a constant amount, but restoring sorted order after a key drop is a linear-time reposition, not an O(1) rewire.
Θ(N2 log N) would need an extra logarithmic factor inside each decrease-key. Repositioning a node in a linked list is a plain sequential scan, which carries no logarithmic component.
Result. The whole sequence takes O(N2) time, driven entirely by the Θ(N) decrease-key operations at O(N) each.