The GATE Grind

GATE 2020 CS – Question 26

Programming and Data Structures · Linked Lists · 1 mark · Multiple choice

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?

  1. $\Theta(n)$
  2. $\Theta(n\log n)$
  3. $\Theta(n^2)$
  4. $\Theta(1)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\Theta(n^2)$

Explanation

Each sorted insertion into a linked list needs a linear scan, with no binary search possible. Total is $1+2+\dots+n=\Theta(n^2)$.