1

I was reading about sorted linked lists and unsorted sorted lists ... I found this table http://bigocheatsheet.com/

I do not understand what they mean by saying in the third table that a sorted linked list has Merge of O(m+n) while an unsorted sorted list has Merge of O(1)!

What does that mean?

thanks

Improve this question
3
  • To merge lists is to take two (or more) lists and combine them into one list. The reason the merge is O(m+n) for the sorted lists is because you need to place the elements into the correct positions when merging sorted lists. In an unsorted list you don't really care where it is in the list so you can add each element of one list to the start (or any arbitrary position) of the second list. Commented Jan 8, 2016 at 19:23
  • Probably this might clear few of your doubts stackoverflow.com/questions/487258/… Commented Jan 8, 2016 at 19:31
  • thank you .. it was helpful ,, God bless you :) Commented Jan 8, 2016 at 19:35

1 Answer 1

Reset to default
1

It's saying that the optimal time to merge a sorted list is O(m + n), because you have to traverse both lists, compare the top/bottom and decide which is higher / lower. Unsorted list could in theory be merged in O(1) if this is a linked list... you just point the tail of the first linked list to the second linked list

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Yes, though I am uncertain that the OP will necessarily recognize for himself the implicit assumption that the resulting list is expected to be the same kind (sorted or not) as the originals. It is ensuring the sortedness of the result that takes more work for the sorted inputs.
@AllaSlda, you only need to traverse each list once (the traversals proceed together). This kind of merge is used in merge sort; you can probably find a more detailed explanation as part of an explanation of that algorithm.
So if it was traversing each list more than one time then it will be O(m*n) !! Do I think correctly ... thank you
@AllaSlda O (m * n) means that for every m element, you are going through all n elements in the other list. Your statement "... traversing each list more than one time..." is ambiguous
@AllaSlda not necessarily. A full explanation of big-O notation would not be appropriate for this site, much less for a comment. Talk to your instructor or find an instructional resource.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.