GATE CS 2016 Set 2 Q.25 (CS Q.15): Arrays and Linked Lists

$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: $\Theta(N)$ delete, $O(\log N)$ insert, $O(\log N)$ find, and $\Theta(N)$ decrease-key. What is the time complexity of all these operations put together?

$O(\log^2 N)$

$O(N)$

$O(N^2)$

$\Theta(N^2 \log N)$

Official answer and solution

Official answer: C
From: Official GATE 2016 answer key

Solution

Determine the time complexity of each individual operation on a sorted doubly linked list and sum them up.

Analyze each operation on a sorted doubly linked list of size $N$ :

delete: A direct pointer to the target node is provided. Unlinking a node in a doubly linked list requires updating p->prev->next = p->next and p->next->prev = p->prev. This takes $O(1)$ time per operation.
For $\Theta(N)$ delete operations: $\Theta(N) \times O(1) = O(N)$ .

insert: In a sorted doubly linked list, finding the correct position for insertion requires linear traversal from an end. In the worst case, this takes $O(N)$ time per insertion.
For $O(\log N)$ insertions: $O(\log N) \times O(N) = O(N \log N)$ .

find: A doubly linked list does not support random access, so binary search cannot be applied. Searching requires sequential traversal, taking $O(N)$ time per search.
For $O(\log N)$ find operations: $O(\log N) \times O(N) = O(N \log N)$ .

decrease-key: A direct pointer to the node is given. When a key is decreased, its sorted position shifts towards the front of the list. Re-positioning the node requires traversing backwards past smaller elements, which takes $O(N)$ time in the worst case.
For $\Theta(N)$ decrease-key operations: $\Theta(N) \times O(N) = O(N^2)$ .

Combine the time complexities of all operations:

\text{Total Time} = O(N) + O(N \log N) + O(N \log N) + O(N^2) = O(N^2)

Therefore, the overall time complexity is $O(N^2)$ , corresponding to option (C).

Final answer

Common trap

Assuming find or insert takes $O(\log N)$ by confusing a sorted linked list with a balanced binary search tree.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 25 of 65, printed as CS Q.15
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source