CODEWITHSUNDEEP
javaalgorithmcomplexity-theoryspace-complexity
JavaDeveloper
JavaDeveloper

Reputation: 5660

Does return value account for space complexity

Below is an algorithm which is used to generate multiple sets. Precisely it solves the following question Print all combination of element in the array such that first element of array is d and next element in the array can be +1 or -1 the previous element in the array. Code was required. Input: num=4, level=3. Output - 4, 3, 2 || 4, 3, 4 || 4, 5, 4 || 4, 5, 6.

This question does not uses int[] arr = new int[level] as a data store which eventually gets copied into a list of int arrays.

What is the space complexity of the following code ? Is it O(level) ie the storage used to solve the problem or is it O(2^level - 1) ie the size of the return type ?

public static List<int[]> getCombinations(int num, int level) {
        final List<int[]> combinations = new ArrayList<int[]>();
        int[] arr = new int[level]; 
        computeCombinations(num, level - 1, 0, combinations, arr);  // note : its level - 1, since currentlevel is set to 0.
        return combinations;
    }


    private static void computeCombinations(int num, int level, int currLevel, List<int[]> list, int[] arr) {
        arr[currLevel] = num;

        if (currLevel == level) {
            // list.add(arr);  <- wrong to do it so
            int[] temp = new int[arr.length];
            System.arraycopy(arr, 0, temp, 0, arr.length);
            list.add(temp);
            return;
        }

        computeCombinations(num - 1, level, currLevel + 1, list, arr);
        computeCombinations(num + 1, level, currLevel + 1, list, arr);
    }

Upvotes: 1

Views: 863

Answers (1)

Zim-Zam O&#39;Pootertoot
Zim-Zam O&#39;Pootertoot

Reputation: 18148

The space complexity accounts for the amount of live memory used by the algorithm, therefore the ArrayList<int[]> factors in to the complexity. However, the algorithm description given at the top of your post says that you only need to print the combinations, not return them; if you immediately print out your combinations after you create them and then discard them (i.e. destructively update the combination rather than making a copy of it) then you'll improve your space complexity.

Upvotes: 3

Related Questions