Subsets - Time/Space Analysis

Question

The problem was to generate the subsets for a given array of integers.
For example,
input: [0, 1, 2]
output: [[], [0], [1], [2], [0,1], [0,2], [1, 2], [0, 1, 2]]
I wanted help on analyzing the time and space complexity of my solution for this problem.

Time Complexity
Like I know that the total number of subsets would be 2^N so the time complexity would be at least 2^N and then the height of my tree would be like worst-case at N, but then I am executing the recursion inside 2 nested loop dependent on N...So I was wondering if my time complexity would be like O(2^N * N^3)? Well, if that was the case ... my code is pretty bad.

Space Complexity
The space would consume 2^N rows and at most N elements, so I understand that the space complexity would be O(2^N * N).

Please let me know if iI misunderstood anything! Thank you.

def powerset(array):
    # Write your code here.
    start_len = 0
    answer = [[]]
    while(start_len <= len(array)):
        i = 0
        while(i < len(array)):
            print(array[i:])
            powersetHelper([], array[i:], start_len, answer)
            i += 1
        start_len += 1
    print(answer)
    return answer


def powersetHelper(chosen, choices, target_len, answer):
    # Write your code here.
    chosen.append(choices[0])
    if(len(chosen) == target_len):
        if(chosen not in answer):
            answer.append(chosen)
    else:
        i = 1
        while(i < len(choices)):
            chosen_copy = chosen.copy()
            powersetHelper(chosen_copy, choices[i:], target_len, answer)
            i += 1

user_16757174 · Answer

This code is actually Ω(N * 4^N) (i.e. at least this runtime), only because of the two lines

        if(chosen not in answer):
            answer.append(chosen)

which perform a linear search over all subsets every time a new subset is added. If your input list has no duplicates and you've written the powerset algorithm to avoid repeats, these lines are unnecessary. Either way, use a set() instead of a list for containment checks, as this by far dominates the runtime.

The space complexity of Theta(N * 2^N) is correct; this is optimal if you're storing all subsets. Unfortunately I don't know the time complexity of the code if that containment check problem is fixed. It looks like a large amount of unnecessary work and recursive calling is performed in powerset and powersetHelper, and I'm having a hard time following the logic of the algorithm. From empirical testing (putting global counters in the function), the number of operations after fixing the containment check grows very very closely to a constant multiple of n^2 * 2^n.

Subsets - Time/Space Analysis

1 Answers