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?

CodePudding user response：

A vector<vector<int>> is under the hood a vector of pointers to independent vectors. In the worst case scenario you will append and the entire vector of pointers will be copied. That is not strictly O(N) if N refers to the total number of elements within the matrix.

CodePudding user response：

The complexity would be O(1) amortized. This is because the std::vector struct is always the same size, and contains a pointer to its contents on the heap. If you add an vector to a vector, only the std::vector structure will be added to the vector, which has a fixed size.

Of course, the vector might have to reallocate itself if it has run out of capacity, which makes the complexity amortized.

CodePudding user response：

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