Question

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: $\Theta$(N) delete, O(logN) insert, O(logN) find, and $\Theta$(N) decrease-key. What is the time complexity of all these operations put together?

• A. O(N)
• B. $\Theta$($N^2$log N)
• C. O($N^2$ )
• D. O($lo{g}^2$ N)

Answer 1

The correct option is C O($N^2$ )

$\begin{array}{cccccc}Datastructureused& Find& insert& Delete& Decreasekey& Overallasympotictime\\ Sorteddoublylinkedlist& O\left(NlogN\right)& O\left(NlogN\right)& O\left(N\right)& O\left(N\right)& O\left(NlogN\right)\end{array}$

Sorted doubly linked list take maxim um of O(N logN) time, but since not present in option
So, go for nearest value O($N^2$).