Project ForgeData Structures
Arrays & Linked Lists
GATE 2020
Easy
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?
- AΘ(n)
- BΘ(n log n)
- Θ(n²)
- DΘ(1)
Explanation
Inserting one element into a sorted linked list of current size m requires traversing up to m nodes to find the correct insertion point — O(m) in the worst case, and a linked list offers no faster way to locate that point (no random access, unlike an array). Inserting n elements one at a time, the k-th insertion costs O(k) in the worst case, so the total cost is O(1+2+...+n) = O(n²) — giving Θ(n²) overall.
Source: GATE CS 2020 (2020)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.