14
\$\begingroup\$

It seems like many users who want to do a challenge don't really think about it how they actually measure "fastness". And then usually a short discussion develops in the comments laying out two possibilities:

  • Scoring by runtime on a benchmark of test cases.
  • Scoring by asymptotic complexity with some tie-breaker.

I think these two goals can make for somewhat different challenges, and we might be able to avoid this discussion if we just had separate tags that clearly imply one of the two winning criteria.

What do you think about retagging the complexity-oriented ones as ? Alternatively, the new tag could be a bit more general to encompass optimisation for space complexity as well.

| |
\$\endgroup\$
  • \$\begingroup\$ I just noticed that there are two tags time-complexity and computational-complexity with one question each. The challenge with the former is actually a popcon and the latter is a code challenge where complexity factors into the score. In any case they should have the same tag (if any), but it might better be different from the one I'd create here which should imply a winning criterion. \$\endgroup\$ – Martin Ender Jul 25 '14 at 10:03
  • \$\begingroup\$ We once had the tag shortest-time which was solely based on runtime. \$\endgroup\$ – Howard Jul 28 '14 at 6:19
7
\$\begingroup\$

Yes, I agree with your proposal. Complexity and runtime speed are different criteria, so having separate tags is a good idea, and people could be interested in runtime speed-oriented challenges but not in complexity-oriented challenges. If we separate the tags, people can filter by this interest, and now they cannot. Also, complexity-oriented challenges don't fit with the current tag wiki:

The runtime speed of the solution is a criterion of this challenge. "Faster, faster would be better."

| |
\$\endgroup\$
  • 4
    \$\begingroup\$ I'll wait a day or two for more feedback, and then I'll create the tag and slowly start retagging appropriate challenges. \$\endgroup\$ – Martin Ender Jul 25 '14 at 9:38
2
\$\begingroup\$

I agree that they should be separated, but I don't think that is necessarily correct. An algorithm is typically language agnostic, or even written in pseudocode. Maybe ?

| |
\$\endgroup\$
  • 7
    \$\begingroup\$ That's a good point but it makes me wonder... why do complexity-based challenges need an implementation at all, except that it acts as a proof-of-concept? Usually, the only thing that's affected by the implementation is some form of tie-breaker. \$\endgroup\$ – Martin Ender Jul 27 '14 at 18:38

You must log in to answer this question.

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