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?

Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Mark Rotteveel, Mar 24 '22 at 11:36
space complexity is also O(n) i think. because it allocates arrays of approximately same size as the input array. it is a measure of memory(or disk) usage. — Lei Yang, Mar 24 '22 at 11:51
So, more than 1 array creation does not affect the space complexity bigO notation? — noob123, Mar 24 '22 at 12:09

Berthur · Accepted Answer · 2022-03-24T12:36:29.577

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.

Space Complexity of the Below Function

1 Answers1