Re: [algogeeks] Time Complexity of Merge Sort(Linked list)
Merge sort is often the best choice for sorting a linked list. Reason because it requires only Θ(1) extra space only and generally beats other algorithms like quicksort,heapsort for sorting linked lists. The overall complexity remain O(N log N) even in the worst case On 6/23/11, Anantha Krishnan ananthakrishnan@gmail.com wrote: Hi All, Can someone explain about the time complexity of Merge sort(Linked list with billions of node)? There is no way to find the middle of sub-list without traversing completely. Please clear my doubts. Thanks Regards, Anantha Krishnan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Time Complexity of Merge Sort(Linked list)
I googled a better explaination for this and found this... hope this will be useful... Sorting a LinkedList is different from sorting an Array as you can not make index based references to any arbitrary item in the List. Instead you need to remember the items during each recursive step and then pass them on to the merge function. For each recursion step you only need to remember the first item of each list half. If you do not remember these items you will quickly end up with indexes, but this leads you to the problem that in your merge-function you need to traverse the whole list with for-loops to find the items to merge. That in turn means you get a complexity of O(n^2). Another important point is the step of recursing into the list and dividing the list in two halves. You can do this step in the recursive part by using for-loops. Contrary to the merge-part at this step the for-loops will only yield a complexity of O(log(n) * n/2) and this is still below the overall O(n*log(n)) complexity. Here is why: 1. You always need to find the first item of each half of list part. 2. In the first recursion step you need to pass the first item and the item at position n/2. This takes n/2 steps to find. 3. In each following step you need to find the middle item for each of the two halves of the list which gives us n/4 to find the item in the first halve and n/4 in the other halve. In total thats n/2. 4. In each following recursive step the amount of list parts double and the lengths is divided by two: * 4 * n/8 in the 3rd recursion depth * 8 * n/16 in the 4th recursion depth, and so on... 5. The recursion depth is log(n) and in each step we perform n/2 steps. This equals O(log(n)*n/2) On 6/24/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: Merge sort is often the best choice for sorting a linked list. Reason because it requires only Θ(1) extra space only and generally beats other algorithms like quicksort,heapsort for sorting linked lists. The overall complexity remain O(N log N) even in the worst case On 6/23/11, Anantha Krishnan ananthakrishnan@gmail.com wrote: Hi All, Can someone explain about the time complexity of Merge sort(Linked list with billions of node)? There is no way to find the middle of sub-list without traversing completely. Please clear my doubts. Thanks Regards, Anantha Krishnan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Time Complexity of Merge Sort(Linked list)
Also u can refer http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html On 6/24/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: I googled a better explaination for this and found this... hope this will be useful... Sorting a LinkedList is different from sorting an Array as you can not make index based references to any arbitrary item in the List. Instead you need to remember the items during each recursive step and then pass them on to the merge function. For each recursion step you only need to remember the first item of each list half. If you do not remember these items you will quickly end up with indexes, but this leads you to the problem that in your merge-function you need to traverse the whole list with for-loops to find the items to merge. That in turn means you get a complexity of O(n^2). Another important point is the step of recursing into the list and dividing the list in two halves. You can do this step in the recursive part by using for-loops. Contrary to the merge-part at this step the for-loops will only yield a complexity of O(log(n) * n/2) and this is still below the overall O(n*log(n)) complexity. Here is why: 1. You always need to find the first item of each half of list part. 2. In the first recursion step you need to pass the first item and the item at position n/2. This takes n/2 steps to find. 3. In each following step you need to find the middle item for each of the two halves of the list which gives us n/4 to find the item in the first halve and n/4 in the other halve. In total thats n/2. 4. In each following recursive step the amount of list parts double and the lengths is divided by two: * 4 * n/8 in the 3rd recursion depth * 8 * n/16 in the 4th recursion depth, and so on... 5. The recursion depth is log(n) and in each step we perform n/2 steps. This equals O(log(n)*n/2) On 6/24/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: Merge sort is often the best choice for sorting a linked list. Reason because it requires only Θ(1) extra space only and generally beats other algorithms like quicksort,heapsort for sorting linked lists. The overall complexity remain O(N log N) even in the worst case On 6/23/11, Anantha Krishnan ananthakrishnan@gmail.com wrote: Hi All, Can someone explain about the time complexity of Merge sort(Linked list with billions of node)? There is no way to find the middle of sub-list without traversing completely. Please clear my doubts. Thanks Regards, Anantha Krishnan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Time Complexity of Merge Sort(Linked list)
Thanks. I think if we make k traversals at each step it would be O(n * n/2 * log n) If I know value of K we can do it in O(n log n) I agree. What will be the time complexity if there are billion nodes i.e even if i know node count i cannot store it in integer variable? Thanks Regards, Anantha Krishnan On Fri, Jun 24, 2011 at 12:58 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: Also u can refer http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html On 6/24/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: I googled a better explaination for this and found this... hope this will be useful... Sorting a LinkedList is different from sorting an Array as you can not make index based references to any arbitrary item in the List. Instead you need to remember the items during each recursive step and then pass them on to the merge function. For each recursion step you only need to remember the first item of each list half. If you do not remember these items you will quickly end up with indexes, but this leads you to the problem that in your merge-function you need to traverse the whole list with for-loops to find the items to merge. That in turn means you get a complexity of O(n^2). Another important point is the step of recursing into the list and dividing the list in two halves. You can do this step in the recursive part by using for-loops. Contrary to the merge-part at this step the for-loops will only yield a complexity of O(log(n) * n/2) and this is still below the overall O(n*log(n)) complexity. Here is why: 1. You always need to find the first item of each half of list part. 2. In the first recursion step you need to pass the first item and the item at position n/2. This takes n/2 steps to find. 3. In each following step you need to find the middle item for each of the two halves of the list which gives us n/4 to find the item in the first halve and n/4 in the other halve. In total thats n/2. 4. In each following recursive step the amount of list parts double and the lengths is divided by two: * 4 * n/8 in the 3rd recursion depth * 8 * n/16 in the 4th recursion depth, and so on... 5. The recursion depth is log(n) and in each step we perform n/2 steps. This equals O(log(n)*n/2) On 6/24/11, Piyush Sinha ecstasy.piy...@gmail.com wrote: Merge sort is often the best choice for sorting a linked list. Reason because it requires only Θ(1) extra space only and generally beats other algorithms like quicksort,heapsort for sorting linked lists. The overall complexity remain O(N log N) even in the worst case On 6/23/11, Anantha Krishnan ananthakrishnan@gmail.com wrote: Hi All, Can someone explain about the time complexity of Merge sort(Linked list with billions of node)? There is no way to find the middle of sub-list without traversing completely. Please clear my doubts. Thanks Regards, Anantha Krishnan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
