Mikemal's blog

Time complexity.
By Mikemal, history, 21 month(s) ago, In English

When a problem has a time limit of 1 second per test case or anything for that matter, how can I calculate the expected runtime of my program in seconds or ms?

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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

It comes with experience.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

TheRe are MANy iNCompREheNsIBLe opTImiZAtIons iN MoDErN cPu and meMorY. FROm C++COdE TO aSSeMblY Is eNOUGH TO COnsuMe a peRsOn's lIfE. iT IS ALmOsT impOsSiblE To fIND A metHod tO accUrATeLY cALCuLAte tHE time ReQuIred FOr a PrOgram tO RuN.

a MoRe EfFECtivE metHoD Is To EStImATe tHe iNcreMEnTaL COMPLExItY, OR (WHEn THe iNcReMENTAl COmpLexIty IS DifFicult to CAlcUlATE) genERATE thE lArgEst dAta AND run IT lOcaLlY.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I think if the time complexity of your program if f(n), then you must have f(n) <= 10^9 to work. Thats a good heuristic anyways. So 10^5 you can use n * sqrt(n) or nlgn or n time complexity, or n= 10^4 you can use n^2, or n= 30 you can use 2^n (maybe, depends on constant factors). If n=10^9 you need linear time, or something very close to linear like maybe n *lg(lg(n)). More exact than that is just random stuff you learn. Like hashmaps are slow, so it might make a solution with right asymptotic performance not work still.

Almost all problems have time limit 1s or roughly that, so this heuristic works well.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    This is a good comment except you use 1e9 instead of 1e8. I have never seen a linear algo work for 1e9, and if it does it's certainly the exception rather than the rule.

    Even when you get something to a complexity that reaches something like 1e8 (like a n² dp for n = 10000) you need to be really careful about constant factors (recursive dps never work and sometimes the order in which you declare the states in your dp table matters, dp[n][m] might pass but dp[m][n] might not). Saying that checking for 1e9 is a good heuristic is crazy.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmmm. I think I agree with you. I am saying f(n) = 10^9 is an upper bound. Ie if its worse than that, forget it. However, it might not work even if f(n) = 10^9. I think I have done problems in linear time with n = 10^9. I can't find any right now though. Maybe I am wrong and am misremembering.

      https://codeforces.net/blog/entry/12755

      Here I see some people posting scripts to count number of operations on codeforces servers, and get 4 * 10^9 operations albeit with extremely simple code.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe this will help you.

→ Reply