CODEWITHSUNDEEP
c++vectordata-structuresset
Dilshan Sandhu
Dilshan Sandhu

Reputation: 15

What is the time complexity of this code Union Of two Arrays using set_union?

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<int> v1(n);
        vector<int> v2(m);
        for (int i = 0; i < n; i++) {
            cin >> v1[i];
        }
        for (int i = 0; i < m; i++) {
            cin >> v2[i];
        }
        set<int> s1(v1.begin(),v1.end());
        set<int> s2(v2.begin(), v2.end());
        set<int> s3;
        set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(s3, s3.begin()));
        for (auto i : s3) cout << i;
    }
}

This code takes two vectors and unions them? Eg: if the input is 5,4,3,2,1 and 5,4,6 Output will be 1,2,3,4,5,6

I am confused about its time complexity? What is time complexity of creation of a set from a vector? What is time complexity of using set_union function?

Upvotes: 0

Views: 1102

Answers (1)

einpoklum
einpoklum

Reputation: 131547

In your code, you are using std::set's. In the C++ standard library, unfortunately, std::set's are ordered (and we have std::unordered_set). Thus, most of the "hard work" in your code is actually converting the vectors into ordered sets; that takes O(n log(n) + m log(m)) time. The union is - almost certainly - linear, as @StPiere suggests, so an additional O(n+m) time.

Upvotes: 1

Related Questions