# What is it's time complexity? As you can see in the above picture that I got an AC in the problem ABCDEF of SPOJ with a time of 2.64 seconds but on the problem page the time limit is mentioned as 1 second. Then why did I get an AC?

unexpected good things happen to good people i guess lol

4 Likes

I also got AC at 6 sec for some other question. Its time limit was 1 s.

1 Like

Here is my code for the problem:

``````#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)

int main()
{
FASTIO
int n;
cin >> n;
vector<int> s(n);
rep(i,0,n) cin >> s[i];
map<int,int> x, y;
rep(i,0,n)
{
rep(j,0,n)
{
rep(k,0,n)
{
x[s[i]*s[j]+s[k]]++;
}
}
}
rep(i,0,n)
{
if(s[i] == 0) continue;
else
{
rep(j,0,n)
{
rep(k,0,n)
{
y[s[i]*(s[j]+s[k])]++;
}
}
}
}
int ans = 0;
for(auto i = x.begin(); i != x.end(); i++)
{
auto j = y.find(i->first);
if(j != y.end()) ans += (i->second)*(j->second);
}
cout << ans << "\n";
return 0;
}
``````

If I am not wrong then the time complexity for this solution should be 3*(n^3)*log(n), and it is well enough for the given constraints. So I don’t understand why the time is 2.64 seconds whereas the time should be within 1 second as per the time complexity.

Have I calculated the time complexity correctly?

I think so

I think SPOJ reports the total time taken over all test files, not the maximum. I can’t seem to find the source for this anymore, but it makes sense, at least.

2 Likes

@galencolin Is my calculation of the time complexity correct?

I think so