What is the worst case time complexity of inserting 'n' element into an empty…
2026
What is the worst case time complexity of inserting 'n' element into an empty linked list of the linked list need to be maintained in sorted order?
- A.
θ (1)
- B.
θ (n2)
- C.
θ (n)
- D.
θ (n log n)
Attempted by 323 students.
Show answer & explanation
Correct answer: B
Inserting an element into a sorted linked list requires traversing existing nodes to find the correct position, taking O(k) time where k is the current list size. When inserting n elements sequentially into an initially empty list, the total time complexity is the sum of integers from 1 to n-1. This summation results in a quadratic time complexity of θ(n^2).