What is the time-complexity of this program (c++)

Question

Code:

#include <iostream>
#include <vector>
 
template<typename T>
std::vector<T> flatten(std::vector<std::vector<T>> const &vec)
{
    std::vector<T> flattened;
    for (auto const &v: vec) {
        flattened.insert(flattened.end(), v.begin(), v.end());
    }
    return flattened;
}
 
int main()
{
    std::vector<std::vector<int>> vec {
        { 1, 2, 3 }, { 4, 5 }, { 6, 7, 8, 9 }
    };
 
    std::vector<int> flattened = flatten(vec);
    for (int &i: flattened) {
        std::cout << i << ' ';
    }
 
    return 0;
}

Is the time complexity of the above code O(n) or O(n^2)? I know it is only a single for() loop, but will using insert() inside of a for loop will make it O(n^2)?

Answer 1

O(Σ_i=0ⁿ m_i),

Where n is the size of the outer vector and m_i is the size of the ith inner vector.

If the size of the outer vector and the size of the inner vectors are all O(n), that's equivalent to O(n²).