thecortex's blog

How to Assess Run Time?
By thecortex, history, 8 years ago, In English

Hello,

I don't know how to relate my asymptotic analysis for a program to run time in millisecond? For example, if I write a solution that runs in O(N^2), how long in milliseconds does it take to run?

Thanks in advance!

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The runtime of an O(N2) solution will depend on the value of N.

The amount of operations you can do in a second is dependant on the complexity of the operations themselves. 5 * 108 simple additions and subtractions can fit into a 1 second time limit, but 108 division and modulo operations probably won't. That being said, I think it's pretty safe to assume 108 operations will take one second.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Your answer is just great and doesn't need any clarification, but I just want to clarify anyway just in case somebody is still stuck.

    You should evaluate the function that describes the asymptotic behavior of your algorithm using the maximum possible values in the constraints as values for the variables.

    For example your O(N2) algorithm when the constraints are 1 ≤ N ≤ 10000 will give you 100002 = 108.

    Now that you have a basic number to start with, as tenshi_kanade said, 108 is in the limit of what may pass in one second, so you should be very careful with your code to keep the constants low. If the result were greater that 108 then is likely it will fail unless it is a very simple code.

    For another example O(N * log2(N)) gives you ~28 900 000 when N ≤ 100000 so again, it is ≤ 108 so it will likely pass.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +2 Vote: I do not like it

    Codeforces servers are Pretty Fast:

    That's 10^9 loop iterations, each of which is at least 5 processor operations (cmp, jge, add, add, jmp), in 841ms. Of course, this code requires little to no memory accesses so it's a bit contrived.

    It's not a good idea to count on this though; you should set your thershold to something like 10^7 when calculating from time complexity to account for the constant factor.

    → Reply