You are not logged in. Please login at to post your questions!


knowing running time from given algorithm complexity

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++.


asked 08 Aug '13, 22:37

boochman's gravatar image

accept rate: 0%

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

cyberax's gravatar image

3★cyberax ♦
accept rate: 20%

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

sid_gup's gravatar image

accept rate: 14%

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.


answered 08 Aug '13, 22:46

tijoforyou's gravatar image

accept rate: 15%

I'm not sure about it but I think 10^-6 is too easy

(08 Aug '13, 23:22) boochman5★

I even think 10^7 will pass easily, under a second. (Not sure, though.)

(08 Aug '13, 23:26) tijoforyou2★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 08 Aug '13, 22:37

question was seen: 4,738 times

last updated: 10 Aug '13, 23:25