0
$\begingroup$

I was solving a question on LeetCode, where I had to generate all possible subsets of a given set of numbers.

Although, the solution makes sense to me, I am unable to understand the derivation of time complexity for those solutions.

A solution I found there was:

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs = {{}};
        for (int num : nums) {
            int n = subs.size();
            for (int i = 0; i < n; i++) {
                subs.push_back(subs[i]);  <---- LINE X
                subs.back().push_back(num); <---- LINE Y
            }
        }
        return subs;
    }
}; 

It is an iterative solution to solve the problem. What I don't understand is the time complexity of the given solution and more importantly, the complexities of Line X and Line Y.

Does copying subs[i] take O(n) time and then pushing back take another O(n) time, or is it an O(1) step?

$\endgroup$
0
$\begingroup$

First tings first:

Line X does a copy subs[i] and creates a new vector. In terms of vector length $n$ this step is $O(n)$.

Line Y is amortized O(1). (The vector might need to reallocate making it O(n) in the worst case; to avoid reallocation see @MSalters post.)

The runtime of the whole procedure is a bit more difficult. At the $i$-th number subs contains every possible subset of all numbers so far. Thus length of subs $=2^i$, but we are interested in how many numbers we need to copy. this can be calculate with the sum of all subset sizes which is $i2^{i-1}$ (meaning at step $i$ we have to copy $i2^{i-1}$ numbers and make $2^i$ push operations). $$O\left(\sum_{i=0}^{n-1} i2^{i-1}+2^i\right) = O(n2^n)$$ The complexity on the right makes sense, all sizes of all vectors in subs will be $n2^{n-1}$ in the end.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

This requires a bit of C++ knowledge.

push_back will copy or move the argument. Copying a vector is O(n), moving it is O(1). In this case, the argument on line X is subs[i], which does not allow a move. It will be copied (good, since we need it later).

On line Y, the argument is just a single integer. Copying an integer is O(1), essentially by definition.

But besides copying the argument, push_back may also need to move all the existing arguments if there's a need to reallocate memory. Vectors have exponential growth, so this doesn't happen on every push_back. As a result, adding N elements to an empty vector will only cause O(log N) realloactions which requires moving O(N) elements.

C++ has a solution to this. vector.reserve(N) will perform one allocation so that push_back up to vector.size()==N will not cause reallocations.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.