How to estimate if a solution will exceed the time limit based on big-O?

Правка en2, от toss, 2015-11-25 00:06:25

Today I completed my second competition (#333) and an important question regarding time limits arose. I solved the B problem in O(n) time and after locking the problem, I saw that a participant in my room solved it in O(n^2) time. Consequently, I wanted to hack his solution based on the given time limit, but I wasn't sure if my challenge would succeed.

So my question is how do you generally estimate if your/someone else's solution would fit the time constraint? I am aware that constants get dropped in big-O, but I am looking for some general rules. For this example, the aforementioned user would perform at least n*(n+1)/2 operations in worst case with n being at most 100 000 and time limit of 2 seconds. Was it reasonable to attempt to hack his solution and what is your approach with regard to the time limit?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский toss 2015-11-25 00:06:25 89
en1 Английский toss 2015-11-25 00:04:23 892 Initial revision (published)