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

Question

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?

Answer 1

The space consumed by the stack should absolutely be taken into consideration, but some may disagree here (I believe some algorithms even make complexity claims ignoring this - there's an unanswered related question about radix sort floating around here somewhere).

Since we split the array in half at each recursive call, the size of the stack will be O(log n).

So, if we take it into consideration, the total space will be O(n + log n), which is just O(n) (because, in big-O notation, we can discard asymptotically smaller terms), so it doesn't change the complexity.

And for creating a local array, a similar argument applies. If you create a local array at each step, you end up with O(n + n/2 + n/4 + n/8 + ...) = O(2n) = O(n) (because, in big-O notation, we can discard constant factors), so that doesn't change the complexity either.

Answer 2

Because you are not calculating the space-complexity when you are doing that. That is called determining: you are doing tests and try to conclude what the space complexity is by looking at the results. This is not a mathematical approach.

And yes, you are right with statement 2.