Time Complexity push_back C++

Question

I'm wondering if we have a matrix declared as vector<vector<int>> matrix and we want to push back to the matrix another vector let's say vector<int> array = {1, 2, 3}, what would be the time complexity of matrix.push_back(array)?

My guess would be O(n) because when we are appending to the matrix the array, all the elements from the array are copied and added separately, until we fill the the whole "row" in the matrix. I'm not really sure. I'm thinking it could be also O(1) beacause maybe cpp could be considering matrix.push_back(array) similar to array.push_back(5), which is clearly O(1). What do you think, guys?

Answer 1

There are 2 scenarios here:

1. The capacity of matrix is at least 1 larger than the old size. In that case simply using matrix.push_back needs to copy every element in array, so the complexity is O(array.size()). This could be improved to O(1) by simply moving array: matrix.push_back(std::move(array));

2. The capacity of matrix matches its size before the insert. In this case the vector class has to allocate new storage for the elements and move every element. Each of the move operations takes O(1) so and depending on whether you move the array or not the complexity is O(matrix.size()) or O(matrix.size() + array.size()).

The second alternative is clearly the worst case scenario and needs to be used for the calculation of the worst case performance...