Suppose we maintain a linked list of length n in sorted order.What would be the big-Oh notation for the add operation? A)O(1) B)O(n) C)O(n log n) D)O(n²)

Question

Quizplus · Accepted Answer

Since we need to keep the list sorted, we cannot add the new element at a random position. Instead, we need to traverse the list in order to find the correct position for the new element. The worst case scenario is when we need to add the new element at the end of the list, which requires traversing the entire list. Therefore, the add operation has a big-Oh notation of O(n).

Suppose We Maintain a Linked List of Length N in Sorted