Number of Instructions that can be acceptable in 1 second

I am going through a question on codechef, and wondering how much complexity would be accepted. Time limit is 1 second. Can O(NlogNlogN) pass?


I guess, it should.

There is no magic number of high-level instructions/steps that gets executed in a second. But, by virtue of the complexity of the algorithm, O(N2) algorithms might not pass where as O(N log N) should be passing. Again, this is not a necessity. The actual execution time will depend on the hidden constant of the Big-Oh notation.

And there indeed is one way to find out, isn’t? Submit the solution and see if it passes!

1 Like

in some cases 10^7 pass untill very strict conditions are present…

Usually, ~106 steps will easily get executed under a second.

yeah, but I have not coded it, instructions of my algorithm would be about 10^7. So what’s say?

I think it would. With lots of computing power available, 10^7 is good I think. (Although i am not exactly sure on this.)

AFAIK, 10^7 should easily pass. I specified 10^6, as i am sure of that.