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?

The correct option is P: $\Theta \left(1\right)$, Q: $\Theta \left(n\right)$, R: $\Theta \left(n\right)$.

Let's analyze the worst-case time complexity of the meld operation (combining two instances of size $n$ into a single instance of the same data structure) for each of the given data structures step-by-step:

1. Data Structure P: Unsorted doubly linked list with head and tail pointers
To meld two unsorted doubly linked lists, we can simply connect the tail of the first list to the head of the second list, and update the tail pointer of the first list to point to the tail of the second list. Since we already have direct pointers to the head and tail of both lists, this concatenation takes a constant number of pointer updates:
- Set $\text{tail1}\to \text{next}=\text{head2}$
- Set $\text{head2}\to \text{prev}=\text{tail1}$
- Update the combined list's tail pointer to $\text{tail2}$.
Since no traversal is required, the worst-case time complexity is:
$\Theta \left(1\right)$

2. Data Structure Q: Min-heap implemented using an array
To meld two min-heaps implemented as arrays, each of size $n$, we can copy all elements from both heaps into a single new array of size $2n$. Copying the elements takes linear time, $\Theta \left(n\right)$. After copying, we run the standard bottom-up heap building algorithm (frequently referred to as $\text{Build-Min-Heap}$) on the combined array. The time complexity of building a heap of size $N$ from an arbitrary array is $\Theta \left(N\right)$. Here, $N=2n$, so building the combined heap takes $\Theta \left(2n\right)=\Theta \left(n\right)$ time. Thus, the overall worst-case time complexity is:
$\Theta \left(n\right)$

3. Data Structure R: Binary Search Tree (BST)
To meld two Binary Search Trees of size $n$ into a single BST, we can do this efficiently by first converting both BSTs into sorted doubly linked lists (or sorted arrays) using in-order traversal, which takes $\Theta \left(n\right)$ time. Next, we merge the two sorted lists/arrays of size $n$ into a single sorted list/array of size $2n$ using the merge step of Merge Sort, which takes $\Theta \left(n\right)$ time. Finally, we convert the merged sorted list/array back into a balanced Binary Search Tree, which also takes $\Theta \left(n\right)$ time. Summing these linear-time phases, the entire meld operation for BSTs can be completed in:
$\Theta \left(n\right)$

Combining the results for P, Q, and R, we obtain the complexities: P: $\Theta \left(1\right)$, Q: $\Theta \left(n\right)$, R: $\Theta \left(n\right)$.