Complexity for 2 second time limit

general
1

Can we run program up to 10^9 if time limit is 2 seconds?

2 Likes
2

Depending on the constant, 1s is 10^8 to 10^9 (for c++). For beginners calculating the operations per second is ok but as you solve more problems you will get a feel for the runtimes of different algorithms.

9 Likes
3

no
for standard online compiler and ide tools like codechef and other online judges only 10^8 computations per second is acceptable.

you can do upto 2*(10^8) computations only

4

Wow… making claims without experience / evidence to back them up

10^9 operations in 0.63s

7 Likes
5

i answered as per codechef platforms meaning for 2 seconds not for other platforms basicaly all time limits depends on environment and machines for your 1 machine 1 second is different and for mine 1 second is different as per what I thought of pardon for any mistake brother

6

I know I am inexperienced but I am learning too…

1 Like
7

Well, you can run this on CodeChef IDE, and it takes 0.95 seconds.

4 Likes
8

OK Let me submit a solution for a question whoose time limit is 2 seconds and computations are 10^9.

1 Like
9

I’m not saying 10^9 is always possible, I’m saying that it is sometimes possible.

“you can do upto 2*(10^8) computations only” applies to some algorithms and not others

4 Likes
10

exactlt what I meant but I was not able to properly deliver what I meant by the way thank you for increasing my knowledge and also sorry for my utter rudeness. you are big and I shall tell you brother

2 Likes
11

again apolozising you for my words.

2 Likes
12

Thing is, X operations per second does not make a lot of sense to go this deep because it is flawed analysis. Not all operations take same amount of time. Like, say you are able to squeeze 10^9 addition operations, replace them with multiplication, or recursions, or divisions and you will see it will fail.

Each operation has a different cost, so you should only use this analysis when the expected algo fails and you need to optimise the code to squeeze it in.

8 Likes
13

Yea,so on an average just assume 10^7 as the final limit, works well in most cases !

2 Likes
14

I’ve seen some problems with constraints upto 10^7 , and O(n log n) codes getting AC. So apparently, it’s too low. Something like 10^8 may be considered feasible as the upper limit ig.
Also, weak test cases may allow O(n^2) for 10^{10} constraints. * insert evil smile and guilt of exaggeration here *