535 views
Given a circular, doubly-linked list whose contents are sorted in ascending order, what is the run-time complexity for inserting a new element into the list so that it remains correctly sorted? (Including the time required to search for the element’s correct position.)
1. $O(1)$
2. $O(\log \text{N})$
3. $O(N)$
4. $O(\text{N}^{2})$

edited

I think binary search can be applied to linked lists (even the singly ones). Say I have a SLL

1  → 3 → … → 100 and I want to insert 2. Then I can traverse till the mid point taking N/2 time (assuming I maintain a global count variable) and the value there (50) is greater than than the value to be inserted (2) so I keep the left pointer as is and make the right pointer point to node containing 49.

Effective SLL now is: 1 → 3 → … → 49.

Again same steps, the time to traverse till mid (25) is (N/2)/2 = N/4.

So on and so forth the effective time to find the location to insert 2 will be N/2 + N/4 + N/8 .. = $\log _{2} n$. Inserting a new node is O(1) anyways.

I calculated and it comes to be O( N) . Can you confirm?

@Yuvraj Raghuvanshi how n/2 + n/4 + n/8 + ... + 1 = log n ??

And what you're doing is equivalent to linear search.

Ah yes I made a mistake. Comparisons will be O(log n) traversal still is in O(n)

It’s better to take the worst case possible

Assume we have 1<->2<->3<->4 in the list

new node to be added is say 5

so to maintain the linked list in the sorted order we have to go to the last node to insert this new node

which takes O(n) time if we n elements

so option c is correct

Yes this seems correct.
In this question we  are using liner – serch algorthim(check each element one by one) so O(n) ?
edited
Not only linear search you can also use binary search but the results would be same as in binary search also traversing takes O(n)