CEKPET's blog

Asymptotic of the solution.
By CEKPET, history, 6 months ago, In English

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!

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
6 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I think it should be around $$$1e8$$$.

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

    Is asymptotics taken into account when entering the test?

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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 :)

→ Reply
»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

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

    Good example, and I think his problem is most likely something related to this: miscalculating time complexity.

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

    Thanks!

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by CEKPET (previous revision, new revision, compare).

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for (int i=1;i<=1e9;i++){ //nothing } If you will not write anything inside of for it takes 1 second

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
for (int i=1;i<=10e9;i++){ 
   //nothing 
}

If you will not write anything inside of for it takes 1 second

→ Reply