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! asked 08 Aug '13, 22:37

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. :) answered 09 Aug '13, 22:26

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! :) answered 10 Aug '13, 23:25
