Come identificare la complessità dello spazio aggiuntivo

Ho appena iniziato ad appoggiare il design dell'algoritmo e ora sto riscontrando problemi nell'individuare lo spazio aggiuntivo utilizzato in un algoritmo. Per il programma dinamico, per quanto riguarda gli esempi che ho imparato, come il problema dello zaino, la schedulazione dell'intervallo, l'allineamento della sequenza, creiamo tutti una struttura dati per archiviare i risultati di sotto-problemi e quindi lo spazio addizionale è facile da identificare. Tuttavia, per altri algoritmi, non capisco esattamente in quale fase utilizzeremmo spazio aggiuntivo.

Voglio discutere di unire sort perché mi sta davvero infastidendo. La sua complessità spaziale è O (n) e sembra il mio libro di testo e tutte le spiegazioni online che ho trovato pensano che questo sia un fatto banale. Dicono tutti che abbiamo bisogno di n array di dimensione 1 e quindi la complessità è 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); 
    } 
} 

Questo è un ordinamento di fusione di Geeksforgeeks. Guardando questo codice, sembra che usiamo solo spazio extra nella funzione di unione. Mi sembra che lo spazio extra utilizzato ogni volta sia dagli array temporali L [] e R [], con una dimensione combinata di r-l. Supponiamo per semplicità che vogliamo ordinare 2 ^ n elementi.

Quindi nella fase di base dovremmo unire 2 array di dimensione 1 e faremmo questo 2 ^ (n-1) volte. Utilizzo di matrici temporanee di lunghezza totale 2 ^ n.

Al livello sopra il passo base uniremo 2 array di dimensione 2 e faremo questo 2 ^ (n-2) volte. Utilizzo di matrici temporanee di lunghezza totale 2 ^ n.

...

Avremmo log (2 ^ n) = n strati in totale. Sommando tutta la lunghezza degli array temporanei otteniamo una lunghezza totale di n * 2 ^ n. Sia N = 2 ^ n, la complessità spaziale sarebbe O (N * log (N)).

Qualcuno può segnalare il mio fraintendimento. Questo mi sta facendo impazzire.