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?
Solution :
The correct option is P: , Q: , R: .
Let's analyze the worst-case time complexity of the meld operation (combining two instances of size 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
- Set
- Update the combined list's tail pointer to .
Since no traversal is required, the worst-case time complexity is:
2. Data Structure Q: Min-heap implemented using an array
To meld two min-heaps implemented as arrays, each of size , we can copy all elements from both heaps into a single new array of size . Copying the elements takes linear time, . After copying, we run the standard bottom-up heap building algorithm (frequently referred to as ) on the combined array. The time complexity of building a heap of size from an arbitrary array is . Here, , so building the combined heap takes time. Thus, the overall worst-case time complexity is:
3. Data Structure R: Binary Search Tree (BST)
To meld two Binary Search Trees of size 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 time. Next, we merge the two sorted lists/arrays of size into a single sorted list/array of size using the merge step of Merge Sort, which takes time. Finally, we convert the merged sorted list/array back into a balanced Binary Search Tree, which also takes time. Summing these linear-time phases, the entire meld operation for BSTs can be completed in:
Combining the results for P, Q, and R, we obtain the complexities: P: , Q: , R: .
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.
Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.