\(N\) items are stored in a sorted doubly linked list. For a \(delete\)…
GATE · 2016 · CS · Set 2 · Computer Science & IT
\(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 541 students.
Show answer
Correct answer: C
The worked solution is available to enrolled students.
Video solution available to enrolled students.
Explore the full course: Iocl Engineers Officers Grade A Paper 2