4
\$\begingroup\$

I want to post a challenge where the scoring is based on complexity but I don't know a) how to define this and b) how well it would be received.

As an example, say the FPU (Floating Point Unit) has been disabled and the challenge requires floating point arithmetic. If adding or subtracting two numbers is O(n) points, multiplying would be O(n2) points and dividing would be 2O(n2) points if bit-shifting is not included. I'm not sure if big O notation is the right way to express this, but hopefully you get the idea. So one way of implementing power xy by just multiplying by x (y-1) times would score (y-1)O(n2). Another method might be a lot faster/simpler.

How could I score this and should I even attempt such a thing?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ So the answer with the best time complexity would win? \$\endgroup\$
    – Alex A.
    Feb 16, 2016 at 6:49
  • 5
    \$\begingroup\$ If you want to include factors of 2, O-notation is not the right tool. \$\endgroup\$
    – Peter Taylor
    Feb 16, 2016 at 8:17
  • \$\begingroup\$ It's worth reading about asymptotic computational complexity and big O notation before considering posting a challenge scored by complexity. You'd be measuring how well an algorithm scales rather than the efficiency for a particular input, so a constant factor like 2 would not be relevant. \$\endgroup\$
    – trichoplax is on Codidact now
    Feb 25, 2016 at 12:42

1 Answer 1

Reset to default
3
\$\begingroup\$

We have the tag, which sounds like it'd fit perfectly here.

From the tag description:

Fastest-algorithm competitions are won by the answer with the smallest asymptotic time complexity. For challenges based on actual runtime, use instead.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ I'd like to add that it's a good idea to read the tag wiki, since fastest-algorithm challenges come with some pitfalls, e.g. how to rank complexities that are functions of multiple variables, and that these almost always need a tie-breaker, because there's only so many complexity classes answers will end up with. You should also explicitly specified whether you'll accept algorithm-only answers, which would make finding a tie breaker a bit harder. \$\endgroup\$
    – Martin Ender
    Feb 16, 2016 at 7:33
  • \$\begingroup\$ ...What he said ^ \$\endgroup\$
    – Alex A.
    Feb 16, 2016 at 8:02

You must log in to answer this question.

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