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?
- $\Theta(n)$
- $\Theta(n\log n)$
- $\Theta(n^2)$
- $\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)$.
More Linked Lists questions
- GATE 2017 CS (CS1) Q18 – Consider the C code fragment given below. Assuming that `m` and `n` point to valid…
- GATE 2016 CS (CS2) Q25 – N records are in a sorted doubly linked list. Node pointers are supplied for delete and…
- GATE 2017 CS (CS2) Q23 – A circular queue uses a singly linked list, with value and next-pointer per node and…
- GATE 2010 CS Q46 – For a singly linked list with at least two nodes, fill the blank to move its last node to…
- GATE 2021 CS (CS2) Q45 – Which statement about this C program is correct?
- GATE 2008 CS Q62 – The list contains1, 2, 3, 4, 5, 6, 7. What is its content after this function?
All Linked Lists questions →