javaalgorithmdata-structuressubsetbacktracking

time complexity of returning power set (leetcode 78 subsets)


Why the time complexity of generating power set of given array is O(n * 2^n). The solution which I created or even the solution which is shared on leetcode runs 2^n times. 1 loop to generate 1 subset. I tested the run count as well and it is always meeting 2^n. The solution is given below and the leetcode also mentions the time complexity of their solution as O(n * 2^n). Cant figure out how it is possible.

class Solution {

    private List<List<Integer>> output = new ArrayList();
    private int n;
    private int runStatus=0;

    public void backtrack(int first, ArrayList<Integer> curr, int[] nums) {
        // Add the current subset to the output
        output.add(new ArrayList(curr));
        // Generate subsets starting from the current index
        for (int i = first; i < n; ++i) {
            curr.add(nums[i]);
            System.out.println("runstatus is : "+(runStatus++));
            backtrack(i + 1, curr, nums);
            curr.remove(curr.size() - 1);
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
        ArrayList<Integer> currCombo = new ArrayList<Integer>();
        backtrack(0, currCombo, nums); // One call generates all subsets
        return output;
    }
}

Now, if you track how many times the "System.out.println("runstatus is : "+(runStatus++));" has run, it will always be O(2^n). Please throw some light on this, what I am interpreting incorrectly?


Solution

  • The factor 𝑛 comes from this operation:

    new ArrayList(curr)
    

    This doesn't run in constant time. This initialises a new ArrayList with values taken from cur. This means it takes time relative to the size of the ArrayList. The average size is 𝑛/2, hence the time complexity for the complete algorithm is O(𝑛2𝑛).