N items are stored in a sorted doubly linked list. For a delete operation, a…

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?

  1. A.

    O(log2 N)

  2. B.

    O(N)

  3. C.

    O(N2)

  4. D.

    Θ(N2 log N)

Attempted by 35 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…