##### 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(N |

D |
Θ(N |

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(N

^{2})So Answer

O(N^{2})wht does decrease key operaation means?

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

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

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.