Complexity of assembly built-in?

Question

Consider a challenge:

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

_{(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 fewest-operations, not fastest-algorithm.

---

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.

Answer 1

• 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.