zscoder's blog

Time complexity
By zscoder, 11 years ago, In English

I'm just wondering, how fast should my algorithm be in order to avoid TLE (Time Limit Exceeded)?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Difficult to tell, around 10^8

for N=20, O(2^N) is nice

for N=30, O(N^5)

for N=100, O(N^3)

for N=1000, O(N^2)

for N=100000, O(N lg N)

for N>10^12, you may need to consider O(1)/O(lg N)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly, it depends highly on basic operations you use. for example % (mod) is worth nearly dozens of if operations...

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's not true — integer modulo is fast (exactly as fast as division, to be exact, and integer division is fast nowadays) and floating point modulo is not used that much.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, I had a case where I multiplied 100x100 matrices and in the innermost loop I used integer modulo (long long to be precise) and when I put it in the second loop (from the 3rd one) the time decreased by 1 sec

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Almost everything you mentioned should run longer than 10s, especially for N > 1012. Just the O(N3) and O(N5) are possible, if those are dynamics with low constants.

    For O(2N), anything above N = 20 requires optimization. If N > 108, you should probably try , but there are still peculiar complexities like .

    It's hard to say anything in general, because there are many subtle differences. You really find out what you can afford by experience.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually, CF's comment system messed it up. He didn't separate the list with commas rather he split it with newlines which are unfortunately not seen unless you type <br>

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ow... I thought it was separated by commas. That's why I always use Preview before posting.

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        that means i need to type two new lines to see the actual new line? orz

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks!

→ Reply