1
\$\begingroup\$

Consider a challenge:

Given a positive integer \$n\$, compute \$n^2\$. The solution with the least asymptotic time complexity in terms of \$n\$ wins.

(let's temporarily ignore that it's too boring or too trivial)

  • Is it clear enough?
  • Assume it's clear enough. Consider this C++ answer. On normal machines, int is the same type as int32_t, which can only hold integers in range \$\left[-2^{31}\dots2^{31}-1\right]\$)

    int f(int n){return n*n;}

    Is it a valid answer?

    • If it is, it will likely be compiled to a single assembly instruction.

      imul edi, edi

      What should be its asymptotic time complexity?

    • If it isn't, why?

Note: Challenges can be objectively and unambiguously defined when there is a set of "base" operations that the program can use, for example:

Given a list \$A\$ of positive integers, sort the list \$A\$. You are not allowed to access the list directly, however you can do the following operations by calling black-box procedures:

  • Compare two numbers at index \$i\$ and \$j\$ (call compare(i, j)). Returns signum(A[i] - A[j]).
  • Swap two numbers at index \$i\$ and \$j\$ (call swap(i, j))

The solution with the asymptotically least number of calls to compare function wins.

(yes, this is also trivial, with a provably optimal \$O(n \log n)\$ solution)

However, in that case they will be , not .


Note: PeterTaylor's answer at revision 1's "moreover..." part was pointing out a flaw in the question. Now I've fixed it, as I think that it's better to fix it rather than ask a new question.

\$\endgroup\$
2
  • \$\begingroup\$ The complexity of imul edi, edi is 1. It's a constant time operation. If you really want it to be interesting, you have to make the integers big. \$\endgroup\$ Jul 16, 2018 at 3:23
  • 1
    \$\begingroup\$ I'd close the challenge as unclear unless they specified the range of integers (or indicate that all integers need to be handled), even with fastest-algorithm. But that's the thing, if you bound N, any O(N) algorithm becomes O(1). \$\endgroup\$ Jul 16, 2018 at 3:34

1 Answer 1

2
\$\begingroup\$
  • Is it clear enough?

No, so the rest of the question is moot. To be clear enough, the example question should explain in sufficient detail what types are admissible. For integers, this is actually quite tricky: some languages have built-in big integers; some languages only have big integers; for others the natural type to use would be an array of some integer type, but then you need to consider whether the base is allowed to be different to the size of the type (taking into account that not all languages have unsigned types, and not all languages have signed types) and whether or not it's acceptable to mix endianness; and for others the natural type is a unary string.

Moreover, in many challenges (possibly not this one) the difference between unary representations vs higher bases is very important in strict comparison of asymptotic complexity, which is expressed in terms of the length of the input rather than the represented value of the input. Thus, for example, "Input a positive integer and print the integers from 0 up to and including the input value" is trivially implemented in quadratic time for unary representations, but the length of the output is superpolynomial in the length of the input if the input is given in base 2 or higher.

\$\endgroup\$
2
  • \$\begingroup\$ I don't see how the edit invalidates part of the answer, but the edit does introduce a major error into the question. atomic-code-golf is about the number of "symbols" in the source code, not about the number of function calls made in execution. \$\endgroup\$ Jul 17, 2018 at 6:27
  • \$\begingroup\$ As far as I can see, none of the existing challenges that work with integers specify how to represent integers in memory, such as this or this. Are those clearer than the example question, and if so, why? \$\endgroup\$
    – DELETE_ME
    Jul 20, 2018 at 4:59

You must log in to answer this question.

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