Expected time complexity

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.