$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 571 students.

Explore the full course: Gate Guidance By Sanchit Sir

\(N\) items are stored in a sorted doubly linked list. For a \(delete\)…