Question

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

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

Answer 1

The average case time complexity for inserting N items into a sorted linked list using an inSort operation is O(N), because half the elements must be traversed, on average, to find the proper insertion point.

Step-by-step explanation:

When inserting N items into a linked list and keeping it sorted each insert, an inSort operation, the average case time complexity is O(N). This is because on average, half the elements need to be accessed in order to find the correct insertion point for each new item. Initially, if the list is empty or the element to be inserted is less than all the elements currently in the list, the operation is O(1) as the insertion is at the beginning. However, in the average case, the new element could be located in any position within the list, requiring a traversal of half the existing elements, which results in O(n/2) time complexity. As constants are dropped in Big O notation, this simplifies to O(N).