How to identify additional space complexity

Question

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.

Answer 1

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.