I am going through a question on codechef, and wondering how much complexity would be accepted. Time limit is 1 second. Can O(N*logN*logN) 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(N*logN*logN) 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!

1 Like

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…