Question

Put N items into linked list, keep it sorted each insert (inSort operation). This has a worst-case time complexity of...

a. O(1)
b. O(log N)
c. O(N)
d. O(N²)

Answer 1

Inserting N items into a sorted linked list (inSort operation) has a worst-case time complexity of O(N²), with each item potentially being compared to all others already in the list.

Step-by-step explanation:

When inserting N items into a linked list and keeping it sorted with each insert, or performing what is known as 'inSort' operation, we have to consider the worst-case scenario. In the worst case, each new item has to be compared to each of the elements already in the list until the correct place is found. Therefore, the first item takes O(1), the second may take up to O(2), the third up to O(3), and so on, until the Nth insert may take O(N). The sum of this series (1 + 2 + 3 + ... + N) can be simplified to O(N²), which represents the worst-case time complexity for this operation.