Subsets Generation Using Bitmask in DSA C - Time & Space Complexity

Time Complexity: Subsets Generation Using Bitmask

O(n * 2^n)

Understanding Time Complexity

We want to understand how the time needed to generate all subsets grows as the input size increases.

Specifically, how does the number of operations change when we use bitmasking to create subsets?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void generateSubsets(int arr[], int n) {
    int total = 1 << n; // 2^n subsets
    for (int mask = 0; mask < total; mask++) {
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                // include arr[i] in current subset
            }
        }
    }
}
    

This code generates all subsets of an array by using bitmasking to decide which elements to include.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop checks each element for every subset mask.
• How many times: The outer loop runs 2^n times, and the inner loop runs n times for each outer loop.

How Execution Grows With Input

As the input size n grows, the total subsets double each time, and for each subset, we check n elements.

Input Size (n)	Approx. Operations
10	About 10 * 2^10 = 10,240
20	About 20 * 2^20 = 20,971,520
30	About 30 * 2^30 = 32,212,254,720

Pattern observation: The operations grow very fast, doubling with each increase in n, multiplied by n.

Final Time Complexity

Time Complexity: O(n * 2^n)

This means the time needed grows very fast as input size increases, because we generate all subsets and check each element.

Common Mistake

[X] Wrong: "Generating subsets is just O(2^n) because there are 2^n subsets."

[OK] Correct: We also check each element for every subset, so the inner loop adds a factor of n, making it O(n * 2^n).

Interview Connect

Understanding this complexity helps you explain why generating all subsets is expensive and shows your grasp of exponential growth in algorithms.

Self-Check

"What if we only printed subsets of a fixed size k instead of all sizes? How would the time complexity change?"