why powerset gives 2^N time complexity?
discrete-mathematics, math, recurrence, recursion
Solution
We are doubling the number of operations we do every time we decide to add another element to the original array.
For example, let us say we only have the empty set {}. What happens to the power set if we want to add {a}? We would then have 2 sets: {}, {a}. What if we wanted to add {b}? We would then have 4 sets: {}, {a}, {b}, {ab}.
Notice 2^n also implies a doubling nature. 2^1 = 2, 2^2 = 4, 2^3 = 8, ...
Problem
The following is a recursive function for generating powerset ``` void powerset(int[] items, int s, Stack<Integer> res) { System.out.println(res); for(int i = s; i < items.length; i++) { res.push(items[i]); powerset(items, s+1, res); res.pop(); } } ``` I don't really understand why this would take `O(2^N)`. Where's that `2` coming from ? Why `T(N) = T(N-1) + T(N-2) + T(N-3) + .... + T(1) + T(0)` solves to `O(2^n)`. Can someone explains why ?