Test Index

GATE Computer Science (CS) 2016 Shift 2 Solved Paper

© examsnet.com

Question : 25

Total: 65

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?

O(log²N)
O(N)
O(N²)
Θ (N²log N)

Go to Question:

Prev Question

Next Question