You are not logged in. Please login at www.codechef.com 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++.

Thanks!

asked 08 Aug '13, 22:37

boochman's gravatar image

5★boochman
31247
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. :)

link

answered 09 Aug '13, 22:26

cyberax's gravatar image

2★cyberax ♦
3.4k21955
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! :)

link

answered 10 Aug '13, 23:25

sid_gup's gravatar image

4★sid_gup
8614715
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.

link

answered 08 Aug '13, 22:46

tijoforyou's gravatar image

3★tijoforyou
4.2k52364
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) tijoforyou3★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×214
×108

question asked: 08 Aug '13, 22:37

question was seen: 4,565 times

last updated: 10 Aug '13, 23:25