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 the meld operation on instances of size n of the above data structures? A. P: Theta(1), Q: Theta(n), R: Theta(n) B. P: Theta(n), Q: Theta(n log n), R: Theta(n) C. P: Theta(n log n), Q: Theta(n log n), R: Theta(n^2) D. P: Theta(1), Q: Theta(n log n), R: Theta(n log n)

GATE 2025 · Programming and Data Structures · Time Complexity · medium

Answer: D. P: Theta(1), Q: Theta(n log n), R: Theta(n log n)

  1. Meld for P: Unsorted doubly linked list with head/tail pointers: We have list1 (head1, tail1) and list2 (head2, tail2). Meld: 1. tail1.next = head2 2. head2.prev = tail1 3. result.head = head1 4. result.tail = tail2 This is 4 pointer assignments regardless of n. Complexity: Theta(1).
  2. Meld for Q: Min-heap implemented using array: Given two min-heap arrays each of size n, the meld proceeds by: Option A: Concatenate arrays (O(1) or O(n)) then run build-heap in O(n). This gives O(n). Option B: Insert elements of one heap into the other one by one. Each insertion takes O(log(n)) to O(log(2n)) = O(log n). For n insertions: O(n log n). For arrays, the standard approach when elements from the second heap are inserted into the first is O(n log n). Build-heap approach gives O(n), but the GATE 2025 answer uses O(n log n) suggesting the insertion approach is considered standard here.
  3. Meld for R: Binary Search Tree: Meld of two BSTs of size n: 1. In-order traverse BST1: O(n) — get sorted array A1 2. In-order traverse BST2: O(n) — get sorted array A2 3. Merge A1 and A2 (two sorted arrays of size n): O(n) 4. Build a balanced BST from the merged sorted array of size 2n: O(n log n) Total: O(n) + O(n) + O(n) + O(n log n) = O(n log n) = Theta(n log n).
  4. Match with answer options: P: Theta(1), Q: Theta(n log n), R: Theta(n log n) This matches option D exactly.