GATE CS 2020 Q.26 (CS Q.16): Arrays and Linked Lists

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?

$\Theta(n)$

$\Theta(n \log n)$

$\Theta(n^2)$

$\Theta(1)$

Official answer and solution

Official answer: C
From: Official GATE 2020 answer key

Solution

Analyze the number of node comparisons required to insert n elements sequentially into a sorted linked list.

A singly linked list does not support random access; traversing to the correct insertion position requires linear scanning from the head of the list.

In the worst case (for example, inserting elements in ascending order when scanning from the head, or descending order depending on list orientation), inserting the $i$ -th element into a list that already contains $i - 1$ elements requires traversing all $i - 1$ existing nodes.

Summing the comparisons over all $n$ insertions:

\sum_{i=1}^{n} (i - 1) = 0 + 1 + 2 + \dots + (n - 1) = \frac{n(n - 1)}{2} = \Theta(n^2)

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

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2020 Computer Science and Information Technology (CS)
Question: 26 of 65, printed as CS Q.16
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source