Question About Time Complexity

General Questions
#1

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?

#2

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.

#3

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).

Screen Shot 2021-01-03 at 11.23.21 PM
Screen Shot 2021-01-03 at 11.23.21 PM1424×658 22.3 KB

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).

#4

Ok, thank you for helping me.

#5

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

1 Like
#6

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.

#7

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

#8

Yeah, the difference isn’t necessarily negligible …

#9

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.

#10

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