ronak037's blog

How many loops in 1 sec ?
By ronak037, history, 5 years ago, In English

Basically I want to know how many loops we can iterate in 1 sec because according to me this number is approx 10^6 but in ques A of given link: https://codeforces.net/contest/1341/problem/A, I submitted a solution with brute force by thinking that it takes a maximum of 10^6 loops so I will not tle in system cases but that doesn't happen my solution got tle later and I relook into that solution and also not getting the reason why this solution get tle as it takes a maximum of 10^6 loops. Solution link: https://codeforces.net/contest/1341/submission/77777541. So please anyone explain to me the reason for this. Thank you

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

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it
  1. Put assertions in your code to check your assumption on the number of loop iterations.
  2. Benchmark your code to check which part is using the most amount of time.
→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

There are additional T more loops. So your complexity is O(T*10^6). 10^6 is enough for 1sec but your code runs in 10^6 * 10^3 = 10^9, which is about 10sec.

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

    I considered T already basically it is O(T*10^3).

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

      No. (a-b)*n .... (a+b)*n is 10^6. N is 10^3, b is 10^3.

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

In 1 sec we can run a loop doing 1e8 operations. The problem with your code is that as we have t test cases and can have max value of 1000. Suppose you have 1000 test cases so your code can run 1000*( 1000000 ) operations in some cases as 1e9 > 1e8. It will give you TLE.

→ Reply