What is the expected time complexity of a problem which has a time limit of 2 seconds?
Around 1e9 operations
So 5e8 operations per second?
5e8 seems more like it. 1e9 might be a little over 2 seconds.
Are you sure? 5e8 seems too much for 1 second. I’ve heard that it’s xe7 operations. Not sure though.
2e8 should be a safe bet. But I’ve seen T = 1000, N = 5 \times 10^5 question is codeforces which run under 2 seconds for an \mathcal O(n) approach. However, the sum of N over all test cases might’ve be lesser than that too. But again, online judges are faster and they compile with some optimizations I guess. Not very sure.
1 Like
It should be less than 2e8-5e8 if you are talking about cf division 2 as time limit is not too tight in cf div 2
so if N=10^5 and number of test case is one then its never work for a O(n^2) algorithm right??
Yeah. n = 10^5, \mathcal O(n^2) is 10^{10} operations and that is going to take around 100 seconds.