Hi guys, let’s say we know our algorithm complexity, so we know how many operations(give or take) our program will do, but how to know if it will stand in the time limits?
Let’s say we algorithm with complexity of N*sqrt(N), and N = 10^5, will this algorithm finish in 1 second?
For purpose of this question let’s assume we are using c++.
Thanks!
I am no expert on this topic. But usually, ~106 steps will easily get executed under a second. The usual average value is more than this.
regarding complexity : O(2n) ~ O(1000n).
regarding execution time : O(2n) !~ O(1000n).
thus, we can’t answer your question without knowing what you assume to be “constant time” operation, and what is not. it’s not because operations do not depend on inputs that they take no time to execute on a machine. 
As cyberax says, without knowing how you define a constant time operation, it’s difficult to answer accurately. But you can do some profiling on your own. Write a simple looping program that performs different sorts of computations and submit it on the judge you want to profile. Now apply a binary search on the number of iterations in your program (TLE signifying that you should reduce number of iterations and WA signifying that you should increase the iterations) and find a closer approximation of the time taken. But make sure that your looping program doesn’t get wiped out in compiler optimization. I hope that helps!
I’m not sure about it but I think 10^-6 is too easy
I even think 10^7 will pass easily, under a second. (Not sure, though.)