GATE CS 2016 Set 2 Q15 — Linked Lists

To find the overall time complexity, let us analyze the worst-case time complexity of each operation on a sorted doubly linked list of size $N$:

1. Delete Operation:

   We are given a direct pointer to the node to be deleted. In a doubly linked list, deleting a node when its pointer is known takes $O(1)$ time because we can update its neighbors' pointers directly.

   $$\text{Total time for } \Theta(N) \text{ deletions} = \Theta(N) \times O(1) = \Theta(N)$$
2. Insert Operation:

   To insert an element into a sorted doubly linked list, we must find its correct position by traversing the list sequentially. Since binary search is not possible on a linked list (due to lack of random access), finding the position takes $O(N)$ time.

   $$\text{Total time for } O(\log N) \text{ insertions} = O(\log N) \times O(N) = O(N \log N)$$
3. Find Operation:

   Searching for an element in a linked list requires sequential traversal, which takes $O(N)$ time.

   $$\text{Total time for } O(\log N) \text{ find operations} = O(\log N) \times O(N) = O(N \log N)$$
4. Decrease-Key Operation:

   We are given a pointer to the node. After decreasing its key, the list may no longer remain sorted. To maintain the sorted order, we must move the node to its correct position, which requires traversing the list backwards. In the worst case, this takes $O(N)$ time.

   $$\text{Total time for } \Theta(N) \text{ decrease-key operations} = \Theta(N) \times O(N) = \Theta(N^2)$$

Overall Time Complexity:

Summing the time complexities of all the operations performed in sequence:

Thus, the overall time complexity is $O(N^2)$.