6
\$\begingroup\$

Suppose I'm writing a question, or the like, and I want solutions to have "reasonable run-times". No solutions that would take years to complete, that sort of think. What are good options for conditions to put in the question to make sure this happens?

\$\endgroup\$
13
\$\begingroup\$

Be reasonable

For instance, "Answers should run in seconds or minutes, not hours or days"

Downside: Somewhat subjective, may be computer specific in some cases.

\$\endgroup\$
  • \$\begingroup\$ I like the idea of just being reasonable, it also side-steps the issue of different performance computers etc. as they aren't going to different by orders of magnitude. \$\endgroup\$ – VisualMelon Apr 15 '15 at 12:46
  • \$\begingroup\$ +1 from me, can't vote. \$\endgroup\$ – isaacg Apr 15 '15 at 12:46
  • 2
    \$\begingroup\$ An alternative wording is to give an exact time limit but qualify it with "on a reasonable desktop machine", but that's just personal preference. \$\endgroup\$ – Martin Ender Apr 15 '15 at 12:49
  • \$\begingroup\$ This is still pretty subjective: Is 1.5hr considered minutes or hours? \$\endgroup\$ – Ypnypn Apr 22 '15 at 21:25
  • \$\begingroup\$ It should also be mentioned that this approach (as well as any approach based on actual runtime) puts some languages at a stronger disadvantage than others, which may or may not be what you want. \$\endgroup\$ – Martin Ender Apr 24 '15 at 12:51
0
\$\begingroup\$

Include specific run-time requirements

For instance, "Your solution must run in under 10 minutes on all test cases provided on my machine."

Downside: Not all languages are easily available, requires OP effort. Timing may not be consistent between machines.

\$\endgroup\$
  • 2
    \$\begingroup\$ Also what takes 12 minutes to run on my machine could take 8 minutes on yours. \$\endgroup\$ – Doorknob Apr 15 '15 at 12:36
  • 1
    \$\begingroup\$ Although it's not exact, I like Martin's take on timing. Give a limit and some leeway. Downside: Not precisely objective. \$\endgroup\$ – Geobits Apr 15 '15 at 12:40
  • \$\begingroup\$ -1 from me, can't vote. \$\endgroup\$ – isaacg Apr 15 '15 at 12:48
-4
\$\begingroup\$

Require Good Asymptotics

For instance, "Polynomial run-times only." or "Solutions must be O(n^4)"

Downside: Not all participants will be familiar with asymptotic analysis. Not all algorithms are easy to analyze. May be dependent on fine details of language implementation. Asymptotics may conceal large constant factors.

\$\endgroup\$
  • 1
    \$\begingroup\$ An O(1) algorithm can still take a very long time to run. \$\endgroup\$ – Doorknob Apr 15 '15 at 12:42
  • \$\begingroup\$ -1 from me, can't vote. \$\endgroup\$ – isaacg Apr 15 '15 at 12:45
  • \$\begingroup\$ I do like this. While this may hide large constant factors, it usually doesn't, and it's very objective. Dependence on language implementation might be tricky at times, but issues shouldn't pop up too often. \$\endgroup\$ – John Dvorak Apr 15 '15 at 12:50
-4
\$\begingroup\$

Require Output Demonstration

For instance, "You must have run your solution on all test cases provided, and include the results in your answer, as well as the runtime."

Downside: Advantages faster computers. Only works for cutoffs around the 1 day - 1 week, not more or less.

\$\endgroup\$
  • 1
    \$\begingroup\$ People can also simply copy the results from others. \$\endgroup\$ – Martin Ender Apr 15 '15 at 12:43
  • \$\begingroup\$ @MartinBüttner Yes, or simply know what the output will look like. I'll address this. \$\endgroup\$ – isaacg Apr 15 '15 at 12:44
  • 1
    \$\begingroup\$ I voted this down, but not because posting solutions to test cases is bad. I just think it isn't a solution to this issue. \$\endgroup\$ – Geobits Apr 15 '15 at 12:44
  • 1
    \$\begingroup\$ +/-0 from me, can't vote. \$\endgroup\$ – isaacg Apr 15 '15 at 12:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .