toss's blog

How to estimate if a solution will exceed the time limit based on big-O?
By toss, history, 9 years ago, In English

Today I completed my second competition (#333) and an important question regarding time limits arose. I solved the B problem in O(n) time and after locking the problem, I saw that a participant in my room solved it in O(n^2) time. Consequently, I wanted to hack his solution based on the given time limit, but I wasn't sure if my challenge would succeed.

So my question is how do you generally estimate if your/someone else's solution would fit the time constraint? I am aware that constants get dropped in big-O, but I am looking for some general rules. For this example, the aforementioned user would perform at least n*(n+1)/2 operations in worst case with n being at most 100 000 and time limit of 2 seconds. Was it reasonable to attempt to hack his solution and what is your approach with regard to the time limit?

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

Comments Comments (13)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I just ran a few tests and found that the CF judging servers can do 2.45 * 10 ** 9 integer operations + updates and 1.225 * 10 ** 9 integer comparisons in 1 second (with GNU C++11).

Just multiply the number of operations in a loop by the amount of times it loops and try to estimate using that. You might also want to test the speed of vector and other STL data structures.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

This handy table will answer all of your questions. (Reference: Competitive Programming 3)

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

    Wasn't it that in yesterdays Div1A problem with n <= 400 the O(n^3) solution failed and O(E + V) solution was the right one?

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

      I coded an O(n^3) solution (Floyd-Warshall) and it was fast enough (296 ms).

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

        What is the complexity of my solution then? 2D BFS. Seems like O(N^2 + N^3) to me

        http://mirror.codeforces.com/contest/602/submission/14454922

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

          I'm not sure about the time complexity of your code, but constant factors are important, too. Floyd-Warshall is an efficient algorithm because it only contains three simple loops. Most O(n^3) algorithms are more complex and slower.

          In addition, Java is slower than C++ and LinkedList is slower than ArrayList.

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

            Used ArrayDeque instead of LinkedList — TLE on the same test. Yeah, maybe the constants are the problem.. But I really doubt it, as timelimit is usually 3-5 times higher than needed just to fit these constants.

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

    is this for 1 sec or 2 sec?? @maximaxi

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

      Codeforces works fine with 100M operations for 1 secs, might need some optimization, though.

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

        But i dont get it .... sometimes in codeforces a problem where n=10^5 .. 2 sec limit ... can not pass O(n^2)..or am i wrong?.. the whole whole solution may contain other O(n) operations, like : getting n input with a for loop etc.

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

          because that is 10 billion operations

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

          It is not so different whether it is one second or two seconds. Since the time complexity ignores constant coefficients, the difference in constant times in the time limit is merely an error in most cases.

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

Here is my answer to a similar question. I typically use 4·108 operations per second as a rule of thumb.

→ Reply