Why do space complexity analysis not involve output space?

Question

In the space complexity analysis of the famous program - Running sum of 1-D array, it is observed that the space complexity is O(N) irrespective of returning the solution in the same array or returning the solution in a newly created array.

Even when the program specifies to return the array as an output, why is there no difference in space complexity analysis between these two cases?

Approach 1: Solution with new array as output

public static int[] runningSum(int[] nums) {
        int[] sum= new int[nums.length];

        sum[0]=nums[0];

        for(int i=1;i<nums.length;i++){
            sum[i]= nums[i]+sum[i-1];
        }
        return sum;
    }

Approach 2: Solution with input array as output

    public static int[] runningSumReturnSameArray(int[] nums) {
        for(int i=1; i< nums.length;i++){
            nums[i]=nums[i-1]+nums[i];
        }
        return nums;
    }

Approach 1 and Approach 2 have difference in the space and hence i am expecting it to have difference in respective space complexities.

Answer 1

Both have the same Time complexity O(n).

Space complexity: is the amount of memory space required relative to the size of the input.

for Approach 1: Space complexity is O( n )

means we add memory space in this function of size n ; where n is the size of input

for Approach 2: Space complexity is O( 1 )

since the function space usage remains constant regardless of the input size.

I hope this help

Answer 2

You should know the difference between space complexity and extra space complexity. We often use the definition of "space complexity" assuming actually extra space. Extra space is space that we allocate only for algorithm runtime.

The actual space complexity of both approaches is O(n) because we also count the input data.

But extra space complexity is different:

For approach 1 it is O(n)

For approach 2 it is O(1)