GATE 2025 CS2 Q.38: solution and answer

GATE 2025 · CS2Q.38 · 2 marks · MCQ

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:

P: Unsorted doubly linked list with pointers to the head node and tail node of the list.

Q: Min-heap implemented using an array.

R: Binary Search Tree.

Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size $n$ of these data structures?

(A)
P: $Θ (1)$ , Q: $Θ (n)$ , R: $Θ (n)$
(B)
P: $Θ (1)$ , Q: $Θ (n lo g n)$ , R: $Θ (n)$
(C)
P: $Θ (n)$ , Q: $Θ (n lo g n)$ , R: $Θ (n^{2})$
(D)
P: $Θ (1)$ , Q: $Θ (n)$ , R: $Θ (n lo g n)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The worst-case meld complexities are P: Θ(1), Q: Θ(n), R: Θ(n) — option (A).

Official answer: ASource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

P: Unsorted doubly linked list with head and tail pointers. Melding two such lists means splicing the tail of one list to the head of the other (updating three or four pointers) and setting the new tail pointer. This is a fixed number of pointer operations regardless of list size, so P is $Θ (1)$ .
Q: Min-heap implemented as an array. Repeated insertion of one heap's n elements into the other would cost $Θ (n lo g n)$ , but that is not optimal. Instead, concatenate the two underlying arrays into one array of size $2 n$ — a $Θ (n)$ copy — and then run the standard bottom-up build-heap (heapify) procedure on the combined array. Build-heap on an arbitrary array of size $m$ runs in $Θ (m)$ time (the classical linear-time heap-construction result), so the whole meld is $Θ (n)$ , not $Θ (n lo g n)$ .
R: Binary Search Tree with no balance guarantee. The worst-case-optimal way to meld two arbitrary BSTs of size $n$ is: an in-order traversal of each tree to get its sorted key sequence ( $Θ (n)$ each), a linear merge of the two sorted sequences ( $Θ (n)$ ), and then building a fresh balanced BST from the merged sorted sequence by repeatedly choosing the middle element as root ( $Θ (n)$ ). Every step is linear, so the total worst-case cost is $Θ (n)$ .
Matching P: $Θ (1)$ , Q: $Θ (n)$ , R: $Θ (n)$ to the options identifies option (A) as correct. Option (B) wrongly assumes heap melding needs $Θ (n lo g n)$ (that is the cost of repeated insertion, not the optimal build-heap approach); options (C) and (D) overstate R's or Q's/P's complexity.

KEY IDEA

Melding two structures optimally means using each structure's cheapest correct rebuild strategy: pointer splicing for the linked list (Θ(1)), linear-time array concatenation + bottom-up build-heap for the heap (Θ(n), not the Θ(n log n) of repeated insertion), and in-order flatten + merge + balanced rebuild for the BST (Θ(n) total).

WATCH OUT FOR

Assuming meld of two heaps costs Θ(n log n) by imagining n repeated insertions into one heap, instead of recognizing that concatenating the arrays and running the linear-time (Floyd's) build-heap procedure achieves Θ(n).

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 14 Complexity questions, with notes

GATE 2025 CS2 Q.38: solution and answer

Answer and solution

More Complexity questions