The time complexity of this code to create a powerset from distinct integers is listed as O(n * 2^n) at all places including the Leetcode solution.
I listed the complexity of each step as a code comment and for me the overall complexity is coming out as O(n^2 * 2^n). You can see we are looping over n times on a line of code whose own complexity is O(n * 2^n), thus, shouldn't be the time complexity of this solution be O(n^2 * 2^n)?
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
output = [[]]
for num in nums: # O(n)
output += [curr + [num] for curr in output] # n for adding two lists and then 2^n times so O(n * 2^n)
return output
The code can be rewritten as follows:
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
output = [[]]
for k, num in enumerate(nums):
new_items = [curr + [num] for curr in output] # O(2^k * (k+1))
output += new_items # O(2^k)
return output
The time complexity of the k-th iteration of the loop is O(2^k * (k+1) + 2^k) = O(2^k * (k+2)). To get the complexity of the whole loop, we need to take the sum of the the expressions 2^k * (k+2) from k=0 to k=n-1, This sum is 2^n * n.