N items are stored in a sorted doubly linked list. For a delete operation, a…
2021
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(logN)insert, O(logN)find and Θ(N)decrease-key. What is the time complexity of all these operations put together?
- A.
O(log² N)
- B.
O(N)
- C.
O(N²)
- D.
Θ(N² log N)
- E.
Question not attempted
Attempted by 318 students.
Show answer & explanation
Correct answer: C
Step 1: The delete operation is performed Θ(N) times, and since a pointer to the node is given, each delete takes O(1) time. So, total time for all delete operations is Θ(N).
Step 2: The insert and find operations are each performed O(1) times (since O(log N) is a constant factor for asymptotic analysis), and each takes O(log N) time. So, total time for insert and find is O(log N).
Step 3: The decrease-key operation is performed Θ(N) times. Since the list is sorted, and a pointer to the node is given, we need to find the correct position to reinsert the node after decreasing its key. This requires traversing the list, which takes O(N) time per operation. So, total time for decrease-key is Θ(N) × O(N) = Θ(N²).
Step 4: The overall time complexity is the sum of all operations: Θ(N) + O(log N) + Θ(N²). The dominant term is Θ(N²), so the total time complexity is Θ(N²).