Space complexity of the array passed function

Question

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.

Answer 1

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

• omrlv: I forgot to mention, yes, our lecture notes are based on c++. Thanks for explanation.

Answer 2

You're right to be confused, and your understanding is actually correct.

Clarification of Space Complexity

The space complexity of a function refers to the additional space required relative to the input size.

Understanding Parameter Passing in C

When you pass an array to a function in C, only a pointer to the first element is passed, not the entire array itself. This means that:

• The function does not create a new copy of the array.

• The function just receives a pointer (int* a) that refers to the same memory location as the original array.

Space Complexity Analysis

Looking at your function:

int sumArr(int a[], int size) {
 int sum = 0; // O(1) space (single integer)
 for (int i = 0; i < size; ++i) {
 sum += a[i]; // Just reading existing elements
 }
 return sum; // O(1) space (single integer returned)
}

• The only extra space used is:

  • sum (a single integer) → O(1)

  • i (loop variable) → O(1)

• The array a[] is not copied but accessed via a pointer, which is a fixed-size variable (4 or 8 bytes, depending on the system).

Final Conclusion

• Correct Space Complexity: O(1) (constant space)

• The lecture notes stating O(n) because the array is copied are incorrect, unless they are referring to some other context (e.g., passing by value in a different language like Python or Java).

So, your intuition is absolutely correct—passing an array to a function in C does not create a new copy, and the function runs in O(1) space complexity.

• wohlstad: Note that the OP has not confirmed yet that the code is indeed supposed to be C code.
• wohlstad: Also the answer looks as if it was generated with the help of gen AI (like chat GPT). If this is the case - please see: Generative AI (e.g., ChatGPT) is banned.
• Nafis Ligari: The answer is based on my understanding of how arrays are passed in C. When an array is passed to a function, only a pointer to the first element is passed, not a copy of the array. This means the space complexity is O(1), not O(n). If the lecture notes claim otherwise, they might be incorrect or referring to a different language. If you believe there’s an error in my explanation, I’d be happy to discuss it.