unable to calculate time complexity of below algorithm

Правка en2, от 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??

Problem link

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;

}
Теги #algorithms, #running time

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)