Range for TLE

1

I am a python programmer. I wanted to know the max size of input which will not get a TLE
In cases O(n),O(n*logn),O(n^2)

Time limit=2 sec

Thanx in advance.

1 Like
2

CodeChef compiler has a speed of approx 10^8 Hz. That means your code can run about 10^8 instructions per second.

Time limit 2 secs means your code can follow 2*(10^8) instructions.

So, if there are no internal test cases and

  1. n is 1000, All 3 will work (10^4 is doubtful in O(n^2) that will depend on how much O(1) work is done in your code)

  2. n is 10^5: O(n) and O(n*log(n)) will work and O(n^2) will not work.

  3. n is 10^7: O(n) will work and rest 2 will not work. (Rare case that O(n) works and O(n*log(n)) doesn’t).

Also, don’t worry about Python. CodeChef multiples but time limit by 5 if you submit in Python to compensate for the slow speed of Python.

I hope this helps. :smiley:

5 Likes
3

Adding to this,
if n <= 21, 2^n solutions are accepted.
if n <= 10^9 or n <= 10^18, then only log n or constant time algorithm will pass.

3 Likes
4

Thank you very much

1 Like
5

Thanx

6

yep and if n <= 12
O(n!) solution are also accepted.

1 Like