Determining whether algorithm runs in given time limit

hey guys i am new to competitive coding. Please help me regarding time limit issues.
I am talking with respect to NI02 Problem - CodeChef.
This problem have time limit 3 second.
Q1) Single source shortest path solution have 0( n^2 ) time complexity. How one will detrmine considering (maximum input size)*(#test cases) whether algo will run within time limit.

Q2) I have submitted solution it got executed in 0.88. Can we approximately determine this value or at least maximum value in question 1

Or what is number of operations per second in codechef judging environment.

Approximately 10^8 number of operation per second are run in the coding environment .

You can get an idea if it will run in the time limit this way .

  1. Get an idea of the complexity of the problem .
  2. Get an idea of the total operation it will require .

For example , as complexity is O(n^2) therefore for n=2500 , in the worst case .

Therefore operations = 2500*2500 = 6.25 *10^6 .

Also since there are 10 test cases , therefore operations = 6.25*10^7 .

Since it is less than 10^8 , it will run in the time limit .

1 Like