Fastest-algorithm competitions are won by the answer with the smallest asymptotic time complexity. For challenges based on actual runtime, use [fastest-code] instead.
This tag indicates that the solution with the smallest asymptotic time complexity is the winner of the challenge. Usually, the tightest bound without any constant prefactors is chosen as the complexity to go by.
Things to consider when posting a fastest-algorithm challenge (and a few suggested solutions):
- Which asymptotic bound to choose? The obvious and most common choice is O(...), which is just any upper bound. But since there is no point in reporting your score any larger than the tightest upper bound, this is effectively equivalent to Θ(...).
- What's the tie-breaker? Fastest-algorithm challenges often result in ties, because the number of different complexities if often rather limited for certain problems, and once an optimal solution has been found there is a good chance others will be posted. For these cases, a tie-breaker should always be specified. Common choices are earliest answer, shortest code-length of the given implementation or shortest actual runtime on a given problem set. See fastest-code for details on the latter.
- How to handle multiple input variables? If there are multiple input variables, say
Nit is not obvious how to order complexity classes. Is O(M N²) better or O(M² N)? If one variable is bounded by a function of the other, say M ∈ O(√N) all
Mcan simply be replaced with the corresponding function of
Nto obtain a complexity class of a single variable. If both inputs are independent of each other, some other order has to be defined. One could, for instance, replace all
Nwith a single variable
Kto get a preliminary order. If the OP then specifies whether
Ndominates, ties could be broken by the highest-order discrepancy in favour of the smaller variable.