big-ospace-complexity

Space complexity of the array passed function


I am confused by the space complexity of the function below:

int sumArr(int a[], int size) {
    int sum = 0;
    for (int i = 0; i < size; ++i) {
        sum += a[i];
    }
    return sum;
}

In the notes, it says that the complexity is O(n) because the array is copied directly, so it will take at least as much space as sizeof(a[0]) * n. But to me, the pointer that points the beginning of the array is passed to the function, so I thought the answer is O(1) complexity. Then I looked at the lecture notes and got even more confused.


Solution

  • The space complexity here actually depends on the implementation language.

    The code you posted looks like C (or C++).
    If this is the case, sumArr will use O(1) space, because if you pass an array as an argument for a, it decays into a pointer.

    But in other languages calling sumArr might require to create a copy of the array. In that case the space complexity will be O(n).