unable to calculate time complexity of below algorithm

#	User	Rating
1	tourist	3985
2	jiangly	3741
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3442
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
2	atcoder_official	162
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	nor	150

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;

}

Comments (1)

Show archived | Write comment?

racsosabe

5 years ago, # |

+17

When I started I had the same problems with these kind of complexities, but it's very simple. Let's just use the $$$O$$$ notation to avoid using constants (I don't think it's correct to say that some $$$O(f(n)) \leq O(g(n))$$$, so we'll use this just for simplicity).

First of all, let's notice that the sizes of each $$$v_{i}$$$ sum up to $$$n$$$, thus:

$$$ \sum\limits_{i=0}^{MAX}|v_{i}| = n $$$

So, if we operate the complexities:

$$$ \sum\limits_{i=0}^{MAX}O(|v_{i}|log(|v_{i}|)) + O(1) \leq \sum\limits_{i=0}^{MAX}O\left(|v_{i}|log\left(\sum\limits_{i=0}^{MAX}|v_{i}|\right)\right) + O(1) $$$

This because $$$|v_{i}| \leq \sum\limits_{i=0}^{MAX}|v_{i}|$$$ and $$$log(x)$$$ is an increasing function. The $$$O(1)$$$ is the cost of iterating over the value of $$$i$$$ and accesing it's vector.

$$$ \sum\limits_{i=0}^{MAX}O\left(|v_{i}|log\left(\sum\limits_{i=0}^{MAX}|v_{i}|\right)\right) + O(1) = \sum\limits_{i=0}^{MAX}O(|v_{i}|logn) + O(1) \leq O(logn)\sum\limits_{i=0}^{MAX}|v_{i}| + \sum\limits_{i=0}^{MAX}O(1) $$$ $$$ O(logn)\sum\limits_{i=0}^{MAX}|v_{i}| + \sum\limits_{i=0}^{MAX}O(1) = O(logn)\cdot n + O(MAX) = O(nlogn + MAX) $$$

The final complexity will be $$$O(nlogn + MAX)$$$. However, I think that if you just store the maximum and the minimum value for each $$$i$$$ in, say, arrays $$$maxV_{i}$$$ and $$$minV_{i}$$$ then it can just take $$$O(n + MAX)$$$.

I hope this helped :D

→ Reply

acash's blog