1

I just started leaning about algorithm design and I am now having trouble identifying the additional space used in an algorithm. For dynamic program, as far as the examples I've learnt, such as knapsack problem, interval scheduling, sequence alignment, we all explicitly create a data structure to store results of sub-problems and therefore the additional space is easy to identify. However, for other algorithms, I don't understand exactly at which step we would use additional space.

I want to discuss merge sort because it is really bugging me. The space complexity of it is O(n) and it seems my textbook and all online explanations I've found think this is a trivial fact. They all say that we need n arrays of size 1 and therefore the complexity is O(n).

void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 

    /* create temp arrays */
    int L[n1], R[n2]; 

    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 

    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray 
    j = 0; // Initial index of second subarray 
    k = l; // Initial index of merged subarray 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 

    /* Copy the remaining elements of L[], if there 
       are any */
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 

    /* Copy the remaining elements of R[], if there 
       are any */
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 

/* l is for left index and r is right index of the 
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
        // Same as (l+r)/2, but avoids overflow for 
        // large l and h 
        int m = l+(r-l)/2; 

        // Sort first and second halves 
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 

        merge(arr, l, m, r); 
    } 
} 

This is a merge sort from Geeksforgeeks. Looking at this code, it seems we only use extra space in the merge function. It seems to me the extra space used each time is by the temp arrays L[] and R[], with a combined size of r-l. Suppose for simplicity we want to sort 2^n elements.

Then at the very base step we would merge 2 arrays of size 1 and we would do this 2^(n-1) times. Using temp arrays of total length 2^n.

At level above the base step we would merge 2 arrays of size 2 and we would do this 2^(n-2) times. Using temp arrays of total length 2^n.

...

We would have log(2^n) = n layers in total. Summing up all the length of temp arrays we get a total length of n*2^n. Let N = 2^n, the space complexity would be O(N*log(N)).

Can anyone point out my misunderstanding. This is driving me crazy.

  • Problems related to algorithms and complexity usually find an answer in computer science stack exchange. cs.stackexchange.com - but I didn't find a duplicate although several questions are about merge sort. – Arthur Havlicek Nov 11 '18 at 17:05
2

Although the merge() function allocates temporary arrays, it is not recursive, and the temporary arrays can be discarded after merge() exits. The total allocation at any moment in time during execution never has to exceed the size of the original array. Therefore, the memory consumption is limited by n.

  • Very good. That makes sense to me. – Robert Harvey Nov 3 '18 at 16:16
  • Oh, so you meant we only use a locker of size n because after we're done with the old stuff in it we clear the locker? – Fluffy Skye Nov 3 '18 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.