# Complexity of assembly built-in?

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;}

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

• 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. Jul 16, 2018 at 3:23
• 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). Jul 16, 2018 at 3:34