c++space-complexity

What is the space complexity of this recursive Insertion Sort algorithm?

void recursiveInsertionSort(vector<int> &arr, int n) {
    if (n <= 1)
        return;
    recursiveInsertionSort(arr, n - 1);
    int val = arr[n - 1], j = n - 2;
    for (j = n - 2; j >= 0 && arr[j] > val; --j)
        arr[j + 1] = arr[j];
    arr[j + 1] = val;
}

I thought the space complexity is constant (O(1)), because I am passing the array by reference.

But I was told it is actually O(n). Why is that ?

Solution

  • It is consuming O(N) linear space complexity because in each recursive call you are O(1) space, and the function call is made N times as the size of the array, so the values are occupying O(1) * N spaces, which leads to the overall O(N) space complexity of the algorithm.

    O(1) * N = O(N)