Complexity for 2 second time limit

Can we run program up to 10^9 if time limit is 2 seconds?

Depending on the constant, 1s is 10^8 to 10^9 (for c++). For beginners calculating the operations per second is ok but as you solve more problems you will get a feel for the runtimes of different algorithms.


for standard online compiler and ide tools like codechef and other online judges only 10^8 computations per second is acceptable.

you can do upto 2*(10^8) computations only

Wow… making claims without experience / evidence to back them up

10^9 operations in 0.63s


i answered as per codechef platforms meaning for 2 seconds not for other platforms basicaly all time limits depends on environment and machines for your 1 machine 1 second is different and for mine 1 second is different as per what I thought of pardon for any mistake brother

I know I am inexperienced but I am learning too…

Well, you can run this on CodeChef IDE, and it takes 0.95 seconds.


OK Let me submit a solution for a question whoose time limit is 2 seconds and computations are 10^9.

1 Like

I’m not saying 10^9 is always possible, I’m saying that it is sometimes possible.

“you can do upto 2*(10^8) computations only” applies to some algorithms and not others


exactlt what I meant but I was not able to properly deliver what I meant by the way thank you for increasing my knowledge and also sorry for my utter rudeness. you are big and I shall tell you brother

1 Like

again apolozising you for my words.

1 Like

Thing is, X operations per second does not make a lot of sense to go this deep because it is flawed analysis. Not all operations take same amount of time. Like, say you are able to squeeze 10^9 addition operations, replace them with multiplication, or recursions, or divisions and you will see it will fail.

Each operation has a different cost, so you should only use this analysis when the expected algo fails and you need to optimise the code to squeeze it in.


Yea,so on an average just assume 10^7 as the final limit, works well in most cases !


I’ve seen some problems with constraints upto 10^7 , and O(n log n) codes getting AC. So apparently, it’s too low. Something like 10^8 may be considered feasible as the upper limit ig.
Also, weak test cases may allow O(n^2) for 10^{10} constraints. * insert evil smile and guilt of exaggeration here *