What is the worst case time complexity of inserting n elements into an empty linked list, if the lin

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2020 GATE-CS Data Structures paper.

Q: How can I prepare for GATE-CS Data Structures?

To prepare for GATE-CS Data Structures, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2020 question covers Linked Lists topic.

Q: What is the difficulty level of this question?

This GATE-CS 2020 Data Structures question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

Accepted Answer

Correct Answer: (D) Theta(n log n)Concept -- Optimal Sorted Linked List Construction: Naive insertion sort on a linked list: each of n elements is inserted at the correct sorted position. For the k-th element, finding its position takes O(k) time (scan from beginning). Total time = O(1) + O(2) + ... + O(n) = O(n^2) -- this is the naive approach. However, the question asks for the worst case of the best possible algorithm. The optimal strategy is: insert all n elements at the head (O(1) each = O(n) total), then sort the list using merge sort (O(n log n)). This achieves O(n log n) total time. Since sorting n elements requires Omega(n log n) comparisons regardless of data structure (comparison-based sorting lower bound), and Theta(n log n) can be achieved with the optimal approach, the worst case time complexity is Theta(n log n).

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

Master GATE-CS with Our Test Series

More Questions from Linked Lists

Frequently Asked Questions

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

Master GATE-CS with Our Test Series

More Questions from Linked Lists

Frequently Asked Questions