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 asint32_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)
). Returnssignum(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.
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\$N
, anyO(N)
algorithm becomesO(1)
. \$\endgroup\$