182 views

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)$