kazuya's blog

Number of Operations in 1 second ?
By kazuya, history, 4 years ago, In English

I was solving this problem 1202B - You Are Given a Decimal String... and I got some idea about it but the time complexity for my algorithm was O(10^8) and since time limit mentioned was 2 sec I didn't implement it and decided to look at the editorial, in which author mentioned this : But, it will work only in C++, since the language is fast and 2⋅10^8 basic operations are executed in less than 0.5 seconds. Can someone explain this? (as far as I know up to 10^6 operations can be done in 1 second, so for 2 seconds ~ 2*10^6, right ?).

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

»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I don't know that there is much to explain... You can do closer to $$$2*10^8$$$ operations per second in C++ if those operations are low-level operations (array accesses, additions, bitshifts, multiplies, subtractions, xors, et cetera). Mods and divisions are slightly slower. If you are doing things like hashmap lookups, reading input, or printing output, you can do about $$$10^6$$$ of those per second. If you use Java, the cut-off is maybe 70% what it is in C++, since a lot of things have more overhead, but of course it really depends on what the operations are; sometimes it is closer to 30% of what C++ can do.

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

It completely depends on the type of operations that you are going to use. For example (%) module operation takes much more time than (+) sum operation. If your operations are simple (like + and ×. But not / and %) C++ can do even more than 1e9 operations per second. The second thing that matters is your memory usage. If CPU can store all of the data in cash memory then your code will run way faster than the case that CPU should use RAM!

→ Reply
»
7 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Is 1,5 seconds enough for O(10^10) in c++?

SecondThread

→ Reply