unable to calculate time complexity of below algorithm
Difference between en1 and en2, changed 2 character(s)
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*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??↵

[Problem link](http://codeforces.com/contest/558/problem/B)↵

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 English acash 2019-08-31 07:25:20 2 Tiny change: ' to be O(nnlogn) .The' -> ' to be O(n*n*logn) .The'
en1 English acash 2019-08-31 07:23:53 1582 Initial revision (published)