\(N\) items are stored in a sorted doubly linked list. For a \(delete\)…
2016
\(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(logN)\)\(insert\), \(O(logN)\)\(find\), and \(Θ(N)\)\(decrease-key\). What is the time complexity of all these operations put together?
- A.
\(O(log^2N)\) - B.
\(O(N)\) - C.
\(O(N^2) \) - D.
\(Θ(N^2logN)\)
Attempted by 295 students.
Show answer & explanation
Correct answer: C
Key insight: the decrease-key operations dominate the running time.
There are Θ(N) delete operations. Given a pointer to the record, deleting from a doubly linked list is O(1) each, so total Θ(N).
There are Θ(N) decrease-key operations. Decreasing a key may require moving the node to its correct place in the sorted list; in a doubly linked list this can take Θ(N) in the worst case for a single operation.
Thus the decrease-key work totals Θ(N) · Θ(N) = Θ(N^2), which dominates the overall cost.
The O(logN) insert and O(logN) find counts contribute at most O(N logN) and are lower-order compared to Θ(N^2).
Therefore the total time complexity is Θ(N^2).
A video solution is available for this question — log in and enroll to watch it.