GATE 2020 CS Q.16: solution and answer

Official answer: CSource: Official answer key, GATE 2020 CS (IIT Delhi)

1. To insert a new element into a linked list that is already maintained in sorted order and currently holds k elements, the algorithm must start at the head and walk node by node, comparing the new value against each existing element, until it finds the correct position to splice the new node in.

2. In the worst case (for example, when the n elements arrive in strictly decreasing order, so each new element is smaller than every element already in the list and must be compared against all k existing elements before being inserted at the tail), this single insertion costs Θ(k) time — there is no way to avoid visiting each of the k nodes, because a linked list offers no random access to jump directly to a candidate position.

3. Inserting n elements one at a time, the i-th insertion (for i = 1, 2, ..., n) is performed when the list already holds i − 1 elements, so its worst-case cost is Θ(i − 1). The total worst-case time over all n insertions is therefore Σ (i=1 to n) Θ(i−1) = Θ(0 + 1 + 2 + ... + (n−1)).

4. The sum 0 + 1 + 2 + ... + (n−1) equals n(n−1)/2 = (n² − n)/2, a standard triangular-number identity. As n grows, the n² term dominates and constant/lower-order terms are absorbed by asymptotic notation, so this total cost is Θ(n²).

5. This quadratic bound cannot be improved: unlike a sorted array or a balanced BST, where the search for the correct position can exploit random access or tree structure to run in O(log n) time, a linked list only supports sequential traversal, so the position-search step for each insertion remains linear in the list's current size. Hence the overall worst-case time complexity of inserting n elements into an empty linked list while keeping it sorted is Θ(n²), which is option (C).