Number of Instructions that can be acceptable in 1 second

slash_it · August 8, 2013, 10:30pm

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?

N<10^5

tijoforyou · August 8, 2013, 10:38pm

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(N²) 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!

akashverma_123 · August 20, 2013, 1:46am

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

tijoforyou · August 8, 2013, 10:40pm

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

slash_it · August 8, 2013, 10:44pm

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

tijoforyou · August 8, 2013, 10:49pm

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.