CODEWITHSUNDEEP
javaspace-complexity
data_pi
data_pi

Reputation: 821

Java - Space complexity with array in for loop

I know the time complexity is O(n). But what is the space complexity of this code? Meaning in worst case, what is the maximum amount of space needed? My guess is that it is O(1), since the array already has a constant amount of space, hence the space isn't being incremented.

Code:

public int[] countBits(int num) {
        int[] res = new int[num+1];

        for (int i = 0; i<num+1; i++){
            res[i] = Integer.bitCount(i);
        }

        return res;
    }

Upvotes: 1

Views: 812

Answers (1)

Yahya
Yahya

Reputation: 14062

Space Complexity of an algorithm is total space of the input size including both Auxiliary space and space used by input.

Furthermore, Auxiliary Space is the temporary space used by an algorithm.

In your example, the input (passed parameter num) is included when calculating how much storage is required to create the array new int[num+1]. Likewise, the for-loop will be bigger.

As a conclusion, The Space complexity is O(n) as well as the Time Complexity is O(n).

Upvotes: 1

Related Questions