Sometimes, when I want to solve a problem, a solution comes to me and when I think about its asymptotics(The number of operations performed by the program or the big $$$O$$$), I understand that the solution will not work, but after looking at the solutions of other users, I see that my idea was correct. I don't post the solution right away because I'm afraid of unnecessary attempts. So answer the question: How many maximum operations can be performed in one second(C++)?
UPD: Thanks to everyone who helped!
I think it should be around $$$1e8$$$.
Is asymptotics taken into account when entering the test?
I am not exactely sure what you mean by that, but if you want to ask does it matter if your code works in $$$O(n)$$$, $$$O(n^2)$$$ or any other complexity, it does. For example, if $$$n <= 2 * 10^5$$$, a solution with complexity $$$O(n log n)$$$ will pass as it needs about $$$3.5 * 10^7$$$ operations in the worst case, but $$$O(n^2)$$$ solution won't as it may need more than $$$1e10$$$ operations.
I use usually assume it's 1.5e8 ops a second, works for me
Though it's much better to memorize max time complexities for various values of $$$n, q$$$ (number of queries for example) etc.:
$$$n \leq 10^5$$$ means you can go with $$$O(n$$$ $$$log^2),$$$ $$$O(n\sqrt{n})$$$ and so on. For $$$n \leq 10^6$$$, usually only solutions with $$$O(n$$$ $$$log)$$$ pass. There are exceptions, $$$O(n$$$ $$$log^2)$$$ might pass as well, if you feel like you can't optimize further — try it, you might get lucky :)
You have around $$$10^9$$$ microperations per second. But if you are multiplying, accessing a lot of or large arrays, using modulo and so on, then the number of operations is smaller. It kind of comes with experience to be able to calculate constant factor.
But sometimes the complexity is not straightforward to estimate. You didn't provide any example, so I cannot explain it, but I can give you my own. Take for example Euclid's seeve. It runs trough an array and then in that loop it runs again trough the array. So complexity is $$$O(N^2)$$$? Wrong, it is actually around $$$O(N log N)$$$ with no optimizations and can be made even faster with some.
Good example, and I think his problem is most likely something related to this: miscalculating time complexity.
Thanks!
Auto comment: topic has been updated by CEKPET (previous revision, new revision, compare).
for (int i=1;i<=1e9;i++){ //nothing } If you will not write anything inside of for it takes 1 second
If you will not write anything inside of for it takes 1 second