Space Complexity of the Below Function

Question

    public static int FindEquilibrumPoint(int[] arr)
    {
        int size = arr.Length;

        var prefixSum = new int[arr.Length];
        var suffixSum = new int[arr.Length];

        prefixSum[0] = arr[0];
        suffixSum[size - 1] = arr[size - 1];

        // Prefix Sum
        for (int i = 1; i < size; i++)
        {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }

        // Suffix Sum
        for (int j = size-2; j > 0; j--)
        {
            suffixSum[j] = suffixSum[j + 1] + arr[j];
        }

        for (int i = 0; i < size; i++)
        {
            if (prefixSum[i] == suffixSum[i])
                return arr[i];
        }
        return -1;
    }

I guess the Time Complexity is O(n) But I am confused about how the space complexity is calculated. What is this funcitons Space Complexity?

Answer 1

You allocate two arrays of length n, where n is the size of the input to your algorithm. The rest of the space that you use does not depend on your input (constant space). We can therefore express your space usage (if not counting the input array itself) as:

2n + c

where c is some constant. Now, similarly to time complexity, we can express the space complexity of your algorithm in big-O notation:

O(2n + c) = O(n)

You already seem to know how the big-O notation works in the context of time complexity, so I doubt this step needs to be explained here (the point is that it's the same notation, so the same rules apply). Therefore, your space complexity is O(n), just like your time complexity.