Why is the complexity of the solution O(N*(2^N)) where N is the size of the input array?
I understand that for each iteration, the array of subsets gets doubled if the current item being used to generate the subsets is unique. However, we don’t carry out 2^N operations for every item in the input array. For every iteration through the input array, we carry out 2^i operations to generate the new subsets. Why then is the complexity O(N * (2^N))?
Let’s say we have the input nums = [1, 2, 3]
The initial array of subsets will have a length of 2^0 = 1 ----- [[]]
After the first iteration, len(subsets) will be 2^1 = 2 ------ [[], [1]]
After the second iteration, len(subsets) will be 2^2 = 4 -------- [[], [1], [2], [1,2]]
After the third iteration, len(subsets) will be 2^3 = 8 --------- [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
Once all the subsets have been created, the total number of operations carried out would be the sum of the series 2^0 + 2^1 … 2^N where N is the length of the input array. This sum is equivalent to 2^(N+1) - 1. And this is equivalent to 2^N operations when we discard the least significant portion of the time complexity.
So once again, why do we need to multiply 2^N by N to get a time complexity of O(N * 2^N)?
I’d really appreciate a clear explanation of how the time complexity shown in the lesson was computed. Thanks in advance.