Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Merge sort time and space complexity

Let's take this implementation of Merge Sort as an example

void mergesort(Item a[], int l, int r) { if (r <= l) return; int m = (r+l)/2; mergesort(a, l, m);   ------------(1) mergesort(a, m+1, r); ------------(2) merge(a, l, m, r); 

a) The time complexity of this Merge Sort is O(n lg(n)). Will parallelizing (1) and (2) give any practical gain? Theorotically, it appears that after parallelizing them also you would end up in O(n lg(n)). But practically can we get any gains?

b) Space complexity of this Merge Sort here is O(n). However, if I choose to perform in-place merge sort using linked lists (not sure if it can be done with arrays reasonably) will the space complexity become O(lg(n)), since you have to account for recursion stack frame size? Can we treat O(lg(n)) as constant since it cannot be more than 64? I may have misunderstood this at couple of places. What exactly is the significance of 64?

c) Sorting Algorithms Compared - Cprogramming.com says merge sort requires constant space using linked lists. How? Did they treat O(lg(n)) constant?

d) Added to get more clarity. For space complexity calculation is it fair to assume the input array or list is already in memory? When I do complexity calculations I always calculate the "Extra" space I will be needing besides the space already taken by input. Otherwise space complexity will always be O(n) or worse.

like image 418
Frank Q. Avatar asked Apr 26 '12 23:04

Frank Q.


People also ask

Why is space complexity of merge sort O n?

If merge sort has no memory leaks, then its space complexity is linear O(n). In addition, it is possible (although not always desirable) to implement merge sort in-place, in which case the space complexity is constant O(1) (all operations are performed directly inside the input array).

How is space complexity calculated by merge sort?

Space complexity of merge sort = space complexity of the merging process + size of recursion call stack = O(n) + O(logn) = O(n).

What is the best time complexity of merge sort?

What will be the best case time complexity of merge sort? Explanation: The time complexity of merge sort is not affected in any case as its algorithm has to implement the same number of steps. So its time complexity remains to be O(n log n) even in the best case.

What is the space complexity of merge sorting a linked list?

The mergesort algorithm is recursive, so it requires O(log n) stack space, for both the array and linked list cases. But the array case also allocates an additional O(n) space, which dominates the O(log n) space required for the stack. So the array version is O(n), and the linked list version is O(log n).


2 Answers

a) Yes - in a perfect world you'd have to do log n merges of size n, n/2, n/4 ... (or better said 1, 2, 3 ... n/4, n/2, n - they can't be parallelized), which gives O(n). It still is O(n log n). In not-so-perfect-world you don't have infinite number of processors and context-switching and synchronization offsets any potential gains.

b) Space complexity is always Ω(n) as you have to store the elements somewhere. Additional space complexity can be O(n) in an implementation using arrays and O(1) in linked list implementations. In practice implementations using lists need additional space for list pointers, so unless you already have the list in memory it shouldn't matter.

edit if you count stack frames, then it's O(n)+ O(log n) , so still O(n) in case of arrays. In case of lists it's O(log n) additional memory.

c) Lists only need some pointers changed during the merge process. That requires constant additional memory.

d) That's why in merge-sort complexity analysis people mention 'additional space requirement' or things like that. It's obvious that you have to store the elements somewhere, but it's always better to mention 'additional memory' to keep purists at bay.

like image 20
soulcheck Avatar answered Sep 23 '22 20:09

soulcheck


MergeSort time Complexity is O(nlgn) which is a fundamental knowledge. Merge Sort space complexity will always be O(n) including with arrays. If you draw the space tree out, it will seem as though the space complexity is O(nlgn). However, as the code is a Depth First code, you will always only be expanding along one branch of the tree, therefore, the total space usage required will always be bounded by O(3n) = O(n).

For example, if you draw the space tree out, it seems like it is O(nlgn)

                             16                                 | 16                             /  \                                                          /    \                           /      \                          /        \                         8          8                            | 16                        / \        / \                       /   \      /   \                      4     4    4     4                         | 16                     / \   / \  / \   / \                    2   2 2   2.....................             | 16                   / \  /\ ........................                  1  1  1 1 1 1 1 1 1 1 1 1 1 1 1 1              | 16 

where height of tree is O(logn) => Space complexity is O(nlogn + n) = O(nlogn). However, this is not the case in the actual code as it does not execute in parallel. For example, in the case where N = 16, this is how the code for mergesort executes. N = 16.

                           16                           /                          8                         /                        4                      /                     2                    / \                   1   1 

notice how number of space used is 32 = 2n = 2*16 < 3n

Then it merge upwards

                           16                           /                          8                         /                        4                      /  \                     2    2                         / \                                        1   1 

which is 34 < 3n. Then it merge upwards

                           16                           /                          8                         / \                        4   4                           /                          2                         / \                         1   1 

36 < 16 * 3 = 48

then it merge upwards

                           16                           / \                          8  8                            / \                           4   4                              / \                             2   2                                 /\                                1  1 

16 + 16 + 14 = 46 < 3*n = 48

in a larger case, n = 64

                     64                     /  \                    32  32                        / \                       16  16                           / \                          8  8                            / \                           4   4                              / \                             2   2                                 /\                                1  1 

which is 64*3 <= 3*n = 3*64

You can prove this by induction for the general case.

Therefore, space complexity is always bounded by O(3n) = O(n) even if you implement with arrays as long as you clean up used space after merging and not execute code in parallel but sequential.

Example of my implementation is given below:

templace<class X>  void mergesort(X a[], int n) // X is a type using templates {     if (n==1)     {         return;     }     int q, p;     q = n/2;     p = n/2;     //if(n % 2 == 1) p++; // increment by 1     if(n & 0x1) p++; // increment by 1         // note: doing and operator is much faster in hardware than calculating the mod (%)     X b[q];      int i = 0;     for (i = 0; i < q; i++)     {         b[i] = a[i];     }     mergesort(b, i);     // do mergesort here to save space     // http://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity/28641693#28641693     // After returning from previous mergesort only do you create the next array.     X c[p];     int k = 0;     for (int j = q; j < n; j++)     {         c[k] = a[j];         k++;     }     mergesort(c, k);     int r, s, t;     t = 0; r = 0; s = 0;     while( (r!= q) && (s != p))     {         if (b[r] <= c[s])         {             a[t] = b[r];             r++;         }         else         {             a[t] = c[s];             s++;         }         t++;     }     if (r==q)     {         while(s!=p)         {             a[t] = c[s];             s++;             t++;         }     }     else     {         while(r != q)         {             a[t] = b[r];             r++;             t++;         }     }     return; } 

Hope this helps!=)

Soon Chee Loong,

University of Toronto

like image 169
Chee Loong Soon Avatar answered Sep 20 '22 20:09

Chee Loong Soon