GATE CS 2025 Set 2 Q28 — Arrays, Stacks and Queues

To find the worst-case time complexity for the meld operation on each of the given data structures of size $n$:

P. Unsorted Doubly Linked List (with Head and Tail Pointers)

To meld two unsorted doubly linked lists, $L_1$ and $L_2$:

• Connect the tail node of $L_1$ to the head node of $L_2$.
• Update the tail pointer of the combined list to point to the tail of $L_2$.

Since we have direct pointers to the head and tail of both lists, this operation requires only a constant number of pointer updates, which takes $\Theta(1)$ time.

Q. Min-heap (implemented using an array)

To meld two min-heaps of size $n$ represented as arrays:

• Concatenate the two arrays of size $n$ into a single array of size $2n$. This takes $\Theta(n)$ time.
• Apply the bottom-up heap construction algorithm (Build-Heap) on the combined array of size $2n$.

The time complexity of Build-Heap on an array of size $N$ is linear, i.e., $\Theta(N)$. Here, $N = 2n$, so the heapification takes $\Theta(2n) = \Theta(n)$ time. Thus, the overall worst-case time complexity is $\Theta(n)$.

R. Binary Search Tree (BST)

To meld two BSTs of size $n$ optimally:

1. Perform an in-order traversal of both BSTs to produce two sorted arrays (or lists) of size $n$. This takes $\Theta(n)$ time.
2. Merge the two sorted arrays of size $n$ into a single sorted array of size $2n$. This takes $\Theta(n)$ time.
3. Reconstruct a balanced BST from the merged sorted array. This can be done in $\Theta(n)$ time.

Thus, the overall worst-case time complexity to meld two BSTs is $\Theta(n)$.

Comparing the results:

• $\mathrm{P}: \Theta(1)$
• $\mathrm{Q}: \Theta(n)$
• $\mathrm{R}: \Theta(n)$

This corresponds to Option A.