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

  • 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. – Taelsin Jan 08 '16 at 19:23
  • Probably this might clear few of your doubts http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o – Atri Jan 08 '16 at 19:31
  • thank you .. it was helpful ,, God bless you :) –  Jan 08 '16 at 19:35

1 Answers1

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

ControlAltDel
  • 33,923
  • 10
  • 53
  • 80
  • 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. – John Bollinger Jan 08 '16 at 19:26
  • @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. – John Bollinger Jan 08 '16 at 19:27
  • So if it was traversing each list more than one time then it will be O(m*n) !! Do I think correctly ... thank you –  Jan 08 '16 at 19:29
  • @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 – ControlAltDel Jan 08 '16 at 19:38
  • @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. – John Bollinger Jan 08 '16 at 19:39