Problem Statement
What is the worst-case time complexity of inserting n elements into an empty linked list that must be kept in sorted order?
Explanation
Inserting n elements into a sorted linked list has worst-case time complexity of O of n squared. For each of the n insertions, you potentially need to traverse the entire list to find the correct position, which takes O of n time in the worst case.
When inserting the first element, you traverse 0 nodes. For the second element, you might traverse 1 node. For the nth element, you might traverse n minus 1 nodes. The total operations are 0 plus 1 plus 2 plus dot dot dot plus n minus 1, which equals n times n minus 1 divided by 2, giving O of n squared complexity.
Code Solution
SolutionRead Only
// Inserting in sorted linked list
void sortedInsert(Node head, int data) {
Node newNode = new Node(data);
// Traverse to find position - O(n) per insertion
Node current = head;
while (current.next != null && current.next.data < data) {
current = current.next;
}
// Insert at correct position
newNode.next = current.next;
current.next = newNode;
}
// For n insertions: O(n) * n = O(n^2)