GATE CS 2020 Q16 — Linked Lists

To find the worst-case time complexity of inserting $n$ elements into an initially empty sorted linked list, let us analyze the insertion of each element one by one:

• 1st element: Inserted into an empty list. This takes $\Theta(1)$ time.
• 2nd element: Inserted into a list of size 1. In the worst case, we compare it with the existing element. This takes $\Theta(1)$ time.
• 3rd element: Inserted into a sorted list of size 2. In the worst case, we may need to traverse to the end of the list. This takes $\Theta(2)$ operations.
• $i$-th element: Inserted into a sorted list of size $i-1$. In the worst case, we must traverse the entire list of size $i-1$ to find the correct insertion position. This takes $\Theta(i)$ operations.

Summing the worst-case time complexities for inserting all $n$ elements:

Thus, the worst-case time complexity is $\Theta(n^2)$.