I was looking at the iterative way to generate all subsets from numbers

1,2,3,\cdots,n-2,n-1

The code for it looks like this,

for (int b = 0; b < (1<<n); b++) {
vector<int> subset;
for (int i = 0; i < n; i++) {
if (b&(1<<i)) subset.push_back(i);
}
}

Is this function’s time complexity O(N\cdot 2^N)?

This is the recursive way of how to do it,

void search(int k) {
if (k == n) {
// process subset
} else {
search(k+1);
subset.push_back(k);
search(k+1);
subset.pop_back();
}
}

When I look at this function, I have no idea what the time complexity is for it. How do you guys go on about finding the time complexity of a recursive function?

From that recursive function, the complexity is probably just 2^n, because each recursive call leads to 2 more recursive calls, and so on and so forth.

Yes, because the outer loop iterates 2^N times and the inner loop iterates N times. We need to run an inner loop in O(N) to get all the indexes of the “on” bits of b and add them to the subset.

For the recursive way, I like to mentally think of a tree of recursive calls. In total, k will range from 0 to N inclusive in all the calls to search. k is the level of the call/node in the tree, so the total depth of the tree is N. There is only 1 call at the first level of the tree, but the number of calls/nodes at a specific level doubles each time we increase the level by 1, because each recursive call leads to 2 more recursive calls (as said by SansPapyrus683).

Tree when N=3. Source: CSES.

Thus, we can generate an upper bound of the complexity to be O(N \cdot 2^N), as there are roughly N levels and each level has an upper bound of 2^N nodes.

Of course, for both implementations, O(N \cdot 2^N) can be simplified to just O(2^N).

Ok, thank you for helping me.

O(N\cdot 2^N) is not equivalent to O(2^N)

1 Like

Oh right.

In practice though, N will be a relatively small number so the difference between O(N \cdot 2^N) and O(2^N) will be very small.

What if N = 10? Isn’t 10240 like a huge difference vs 1024?

Yeah, the difference isn’t necessarily negligible …

I personally have never encountered a problem where the time is so tight that the difference of a factor of 10 in the time complexity would have been the difference between the number of operations being too low or too high.

I myself have encountered problems where the difference between TLE and AC was a difference in the constant factor as minor as switching from an ArrayList to an array.

4 Likes