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.

Θ(n)

B.

Θ(nlogn)

C.

Θ(n2)

D.

Θ(1)

Solution:

For calculating the worst-case time complexity we consider that we are inserting in an empty linked list.

T(1) of inserting one element Θ(1)

T(n) of inserting n element Θ(n)

But to maintain the list in sorted order the total cost of n-operations is Θ(n2)

Ambiguity in question: It just states "needs to be maintained in sorted order" but does not specify sorting at each element insertion or sorting the entire linked list after insertion.