What is the worst case time complexity of inserting \(n\) elements into an…
2020
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 ?
- A.
\(\theta (n)\) - B.
\(\theta (n \ log \ n)\) - C.
\(\theta (n^2)\) - D.
\(\theta (1)\)
Attempted by 765 students.
Show answer & explanation
Correct answer: C
Key idea: each insertion may require scanning the list to find the correct sorted position.
Worst-case time for the i-th insertion is O(i) because the list size is about i and you may need to traverse it.
Total worst-case time for n insertions is the sum O(1) + O(2) + ... + O(n) = Theta(n^2).
Therefore the worst-case time complexity of inserting n elements into an empty linked list while keeping it sorted is Theta(n^2).