unable to calculate time complexity of below algorithm

Revision en2, by acash, 2019-08-31 07:25:20

I stuck at a problem ,It was a basically implementation problem ,It passed all the test cases But I have doubt regarding its time complexity.

for (int i = 0; i < 1e6 + 100; i++) {
sort(v[i].begin(), v[i].end());
}


The time complexity of this loop seems to be O(n*n*logn) .Then It should definitely fail because n value can be 10^6.Even O(n*n) fail for such higher value of n,I have seen already so many times on codeforces.

What is its correct time complexity??

Please forgive me if it is too basic!

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1e6 + 100;
vector<int> a, f(1e6 + 100);
vector<int>v[N];
int main() {
int n;
cin >> n;
a.resize(n);
int mx = -1;
for (int i = 0; i < n; i++) {
cin >> a[i];
f[a[i]]++;
v[a[i]].push_back(i);
mx = max(mx, f[a[i]]);
}
for (int i = 0; i < 1e6 + 100; i++) {
sort(v[i].begin(), v[i].end());
}
int diff = INT_MAX;
int ans[2];
for (int i = 0; i < 1e6 + 100; i++) {
if (f[i] == mx) {
int temp = v[i][v[i].size() - 1] - v[i][0];
if (diff > temp) {
diff = temp;
ans[0] = v[i][0];
ans[1] = v[i][v[i].size() - 1];
}
}
}
cout << ans[0] + 1 << " " << ans[1] + 1;

}


#### History

Revisions

Rev. Lang. By When Δ Comment
en2 acash 2019-08-31 07:25:20 2 Tiny change: ' to be O(nnlogn) .The' -> ' to be O(n*n*logn) .The'
en1 acash 2019-08-31 07:23:53 1582 Initial revision (published)