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.
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).