I was solving questions on space complexity and When we talk about space complexity, we don't consider the space used by the input.but here in below code which I saw from a website ,isn't it should be O(1) , why they are saying its dependent on n ?? Please clarify iam confused
int sum(int A[ ], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}
In the above piece of code it requires 'n*2' bytes of memory to store array variable 'a[ ]' 2 bytes of memory for integer parameter 'n' 4 bytes of memory for local integer variables 'sum' and 'i' (2 bytes each) 2 bytes of memory for return value.
That means, totally it requires '2n+8' bytes of memory to complete its execution. Here, the total amount of memory required depends on the value of 'n'. As 'n' value increases the space required also increases proportionately. This type of space complexity is said to be Linear Space Complexity.
Various authors and web-sites use "space complexity" to mean different things, so you have to check the notation for the specific web-page.
https://www.studytonight.com/data-structures/space-complexity-of-algorithms states that Space Complexity = Auxiliary Space + Input space (I assume that is related to the site you used.)
https://theory.cs.princeton.edu/complexity/book.pdf defines Space Complexity as excluding Input Space (and in that case input space is read-only), which seems more normal.