What is the time complexity of this powerset function?

Question

I solved this question (powerset function) from leetcode https://leetcode.com/problems/subsets/submissions/ and here is my solution:

    def subsets(nums):
        res = []
        n = len(nums)
        for subset_id in range(2**n):
            tmp = []
            for index in range(n):
                if 1 << index > subset_id:
                    break
                if subset_id >> index & 1:
                    tmp.append(nums[index])
            res.append(tmp)
        return res

I am having a hard time analyzing the time complexity of this code, the statement if 1 << index > subset_id: break makes it under O(n*2^n) I think but does it take it all the way down to O(2^n) ? I don't know it's hard to tell.

Answer 1

If we assume that the inner loop is going to go through about half of range(n) before hitting the break every time, then this is O(n/2*2^n), which is actually still O(n*2^n). This works for any fixed fraction of the loop, so even if it's a tenth of range(n) on average instead of half, it's still O(n*2^n)