acash's blog

By acash, history, 3 months ago, ,

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;

}

• -3

 » 3 months ago, # |   0 Auto comment: topic has been updated by acash (previous revision, new revision, compare).
 » 3 months 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