subham_kr's blog

Estimating Complexity by given constrains
By subham_kr, 10 years ago, In English

How to estimate the complexity of the code needed to pass the solution by checking the constrains nd time limit ??

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

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

On the modern computers we can do something like 108 trivial operations per second.

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

Basically it depends on the architecture of the system you are running the program. In my experience, on most judges roughly 10^8 operations can run per second. It depends on the language you code. For Slower languages like java and python bring that down by two to three times. Also it depends on the operations you have. Simple operations like addition, subtraction , multiply are fast. Division, modulo are slow operations. There are many more factors involved.

But to sum it up, you can have 10^7-10^8 operations generally while submitting your code on most judges. That means if say you had a problem with array of size N = 1000 and T = 100 such test cases, then you can try out an algorithm of O(N^2) complexity (if it fails try optimizing and reducing constant factors). If N was O(10^5) then a O(N) algorithm would do. If N is very large say 10^18, then go for a O(log(N)) solution or even O(1) solution. In this way, just by seeing the constraints of the problem, you can roughly estimate what complexity it can have at max.

→ Reply