# Time Complexity of inserting a vector to a vector of vectors in C++

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?

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.

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.