Why don't we consider stack frame sizes while calculation Space Complexity of recursive procedures?

Viewed 918

Consider, the case of Merge Sort on an int Array containing n elements, we need an additional array of size n in order to perform merges.We discard the additional array in the end though.So the space complexity of Merge Sort comes out to be O(n). But if you look at the recursive mergeSort procedure, on every recursive call mergeSort(something) one stack frame is added to the stack.And it does take some space, right?

public static void mergeSort(int[] a,int low,int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;
        mergeSort(a,low,mid);
        mergeSort(a,mid+1,high);
        merge(a,mid,low,high);
    }
}

My Questions is :

  1. Why don't we take the size of stack frames into consideration while calculating Merge Sort complexity ?
  2. Is it because the stack contains only a few integer variables and one reference, which don't take much memory?
  3. What if my recursive function creates a new local array(lets say int a[]=new int [n];).Then will it be considered in calculating Space complexity?
2 Answers
Related