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(Log²N)
b)
O(N)
c)
O(N²)
d)
Θ(N² Log N)
Correct answer is option 'C'. Can you explain this answer?

Question

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(Log²N)
b)
O(N)
c)
O(N²)
d)
Θ(N² Log N)

Correct answer is option 'C'. Can you explain this answer?

Answer

The time complexity of decrease-key operation is Θ(1) since we have the pointer to the record where we have to perform the operation. However, we must keep the doubly linked list sorted and after the decrease-key operation we need to find the new location of the key. This step will take Θ(N) time and since there are Θ(N) decrease-key operations, the time complexity becomes O(N²).

Answer

1. Delete the record pointed by pointer P.
2. Decrease the key of the record pointed by pointer Q.

To perform these operations efficiently, we can use the following algorithm:

1. Initialize two pointers, prev and current, to the first node of the doubly linked list.
2. Traverse the list using the current pointer until we find the node pointed by pointer P. Keep track of the previous node using the prev pointer.
3. Once the node pointed by pointer P is found, update the next pointer of the previous node to point to the next node of the current node. Also, update the previous pointer of the next node to point to the previous node of the current node. This effectively removes the node from the list.
4. Traverse the list again using the current pointer until we find the node pointed by pointer Q.
5. Once the node pointed by pointer Q is found, update its key with the desired decreased value.
6. Return the updated list.

The time complexity of this algorithm is O(n), where n is the number of items in the list. This is because we need to traverse the entire list to perform the delete and decrease-key operations. However, the actual time complexity may vary depending on the specific implementation of the doubly linked list.

Similar Computer Science Engineering (CSE) Doubts

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queu e)?

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT ( nrefers to the number of items in the queu e)?

Which of the following is not true about comparison based sorting algorithms?

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company