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?
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𝑛).