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&lt;vector&lt;int&gt;&gt; subsets(vector&lt;int&gt;&amp; nums) {
        vector&lt;vector&lt;int&gt;&gt; subs = {{}};
        for (int num : nums) {
            int n = subs.size();
            for (int i = 0; i &lt; n; i++) {
                subs.push_back(subs[i]);  &lt;---- LINE X
                subs.back().push_back(num); &lt;---- 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.