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?
Correct : a
This question is all about understanding how different data structures behave when you try to combine - or "meld" - two instances of them into one. The trick is knowing the internal structure of each data structure and what the cheapest possible merge strategy looks like for each.
P — Unsorted Doubly Linked List with head and tail pointers: Θ(1)
This one is the simplest. Since we already have a pointer to the tail of the first list and a pointer to the head of the second list, all we need to do is link them together - tail1.next = head2 and head2.prev = tail1. That's it. No traversal, no comparisons, no sorting needed. The list is unsorted, so we don't have any ordering constraints to maintain. The whole operation completes in a fixed number of pointer updates, making it a clean Θ(1).
Q - Min-Heap implemented as an array: Θ(n)
When you meld two min-heaps of size n each, you first concatenate the two underlying arrays to get an array of size 2n. Now this combined array doesn't satisfy the heap property, so you need to restore it. The standard way to do this is the build-heap algorithm - you start heapifying from the last internal node up to the root. Even though each heapify call is O(log n), the total work across all nodes sums up to O(n) - this is a well-known result from the mathematical analysis of build-heap. So the overall meld operation on two min-heaps is Θ(n).
R — Binary Search Tree: Θ(n)
At first glance, people assume merging two BSTs must be at least O(n log n) because inserting n elements one by one into a BST is O(n log n). But there's a smarter approach. You do an in-order traversal of both BSTs - each traversal takes O(n) and gives you a sorted array. Then you merge the two sorted arrays, which is the classic merge step from merge sort - also O(n). Finally, you build a balanced BST from the merged sorted array, which again takes O(n) using the recursive mid-point construction technique. All three steps together make it Θ(n), not Θ(n log n).
So the correct answer is Option A - P: Θ(1), Q: Θ(n), R: Θ(n).
Similar Questions
Total Unique Visitors