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\$
1

4 Answers 4

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\$
5
  • \$\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\$ Apr 15, 2015 at 12:46
  • \$\begingroup\$ +1 from me, can't vote. \$\endgroup\$
    – isaacg
    Apr 15, 2015 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\$ Apr 15, 2015 at 12:49
  • \$\begingroup\$ This is still pretty subjective: Is 1.5hr considered minutes or hours? \$\endgroup\$
    – Ypnypn
    Apr 22, 2015 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\$ Apr 24, 2015 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\$
3
  • 2
    \$\begingroup\$ Also what takes 12 minutes to run on my machine could take 8 minutes on yours. \$\endgroup\$
    – Doorknob
    Apr 15, 2015 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, 2015 at 12:40
  • \$\begingroup\$ -1 from me, can't vote. \$\endgroup\$
    – isaacg
    Apr 15, 2015 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\$
3
  • 1
    \$\begingroup\$ An O(1) algorithm can still take a very long time to run. \$\endgroup\$
    – Doorknob
    Apr 15, 2015 at 12:42
  • \$\begingroup\$ -1 from me, can't vote. \$\endgroup\$
    – isaacg
    Apr 15, 2015 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\$ Apr 15, 2015 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\$
4
  • 1
    \$\begingroup\$ People can also simply copy the results from others. \$\endgroup\$ Apr 15, 2015 at 12:43
  • \$\begingroup\$ @MartinBüttner Yes, or simply know what the output will look like. I'll address this. \$\endgroup\$
    – isaacg
    Apr 15, 2015 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, 2015 at 12:44
  • 1
    \$\begingroup\$ +/-0 from me, can't vote. \$\endgroup\$
    – isaacg
    Apr 15, 2015 at 12:48

You must log in to answer this question.

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