##### What is the time complexity of all these operations put together in a sorted doubly linked list?

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

 A O(Log2N) B O(N) c O(N2) D Θ(N2 Log N)
##### 5Comments
Sumit Verma
22 Jul 2017 02:10 pm

Delete - θ(1) time  directly given
Insert - O(N) time insert at the end of the sorted list
Find - θ(N) time search sequentially
Decrease key - θ(N) time delete then insert

Now using above,
=θ(N) * θ(1) + O(logN) * O(N) + O(logN) * θ(N) + θ(N) * θ(N)
using property of asymptotic notation  O(N2 )
So Answer O(N2

set2018
12 Aug 2017 09:56 am

wht does decrease key operaation means?

shivani
12 Aug 2017 10:17 am

it means decreasing the value of a key , for ex. in heap you want to decrease value of a root node or leaf node or any internal node lets say from  15 to 4 .then it's decrease key operation

set2018
12 Aug 2017 11:56 am

it means we have to go at tht particular node delete tat node after tht new value have to put m in right shivani ?

shivani
12 Aug 2017 02:08 pm

it means , you have to search for node where you want to apply decrease key operation , then apply decrease key and then use heapify operation to satisfy heap property.