×

# knowing running time from given algorithm complexity

 0 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 5★boochman 31●2●4●7 accept rate: 0%

 1 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 3.4k●2●19●55 accept rate: 20%
 1 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 4★sid_gup 861●4●7●15 accept rate: 14%
 0 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 4.2k●5●23●64 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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×224
×115

question asked: 08 Aug '13, 22:37

question was seen: 4,681 times

last updated: 10 Aug '13, 23:25