in DS recategorized by
475 views
9 votes
9 votes
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})$
in DS recategorized by
475 views

4 Comments

edited by

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.

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

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

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

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

1 Answer

7 votes
7 votes
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
edited by

4 Comments

Yes this seems correct.
0
0
In this question we  are using liner – serch algorthim(check each element one by one) so O(n) ?
0
0
edited by
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)
2
2
Answer:

Related questions