Time Complexity: Generate All Subsets Powerset
O(n * 2^n)
0
0
Generate All Subsets Powerset in DSA C - Time & Space Complexity
Understanding Time Complexity
When we generate all subsets of a set, we want to know how the work grows as the set gets bigger.
We ask: How many steps does it take to list every possible subset?
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 i = 0; i < total; i++) {
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
// include arr[j] in current subset
}
}
}
}
This code creates every subset by checking each combination of elements using bits.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Nested loops where outer runs 2^n times and inner runs n times.
- How many times: Outer loop runs once for each subset (2^n), inner loop runs n times per subset.
How Execution Grows With Input
As the input size n grows, the number of subsets doubles each time, and for each subset, we check n elements.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | ~10 * 2^10 = 10,240 |
| 20 | ~20 * 2^20 = 20,971,520 |
| 30 | ~30 * 2^30 = 32,212,254,720 |
Pattern observation: The work grows very fast, doubling with each added element and multiplying by n.
Final Time Complexity
Time Complexity: O(n * 2^n)
This means the time needed grows very fast as the input size grows, because we list all subsets and check each element.
Common Mistake
[X] Wrong: "Generating all subsets is just O(2^n) because there are 2^n subsets."
[OK] Correct: We also spend time checking each element in every subset, so the work multiplies by n, making it O(n * 2^n).
Interview Connect
Understanding this complexity helps you explain why generating all subsets is costly and shows you can analyze nested loops with exponential growth.
Self-Check
"What if we only wanted subsets of a fixed size k? How would the time complexity change?"