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
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
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
2
)
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!
Usually, ~10
6
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.
in some cases 10^7 pass untill very strict conditions are present…