712 views
4 votes
4 votes
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)

Doubt : What is decrease key? Decreasing the value?
and answer to the question.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
Mrityudoot asked Feb 25
144 views
How can we find the highest element in a singly linked list in O(1)? We are free to use any extra space.