### CEKPET's blog

By CEKPET, history, 2 months ago,

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!

• -21

 » 2 months ago, # | ← Rev. 2 →   +8 I think it should be around $1e8$.
•  » » 2 months ago, # ^ |   0 Is asymptotics taken into account when entering the test?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +3 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.
 » 2 months ago, # |   +8 I use usually assume it's 1.5e8 ops a second, works for meThough 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 :)
 » 2 months ago, # |   +13 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.
•  » » 2 months ago, # ^ |   0 Good example, and I think his problem is most likely something related to this: miscalculating time complexity.
•  » » 2 months ago, # ^ |   0 Thanks!
 » 2 months ago, # |   0 Auto comment: topic has been updated by CEKPET (previous revision, new revision, compare).
 » 2 months ago, # |   0 for (int i=1;i<=1e9;i++){ //nothing } If you will not write anything inside of for it takes 1 second
 » 2 months ago, # | ← Rev. 2 →   0 for (int i=1;i<=10e9;i++){ //nothing } If you will not write anything inside of for it takes 1 second