Complexity calculations are riddled with hidden assumptions.
For example, one often refers to Bubble sorting as an
O(n2)-time operation, when, in fact, it is not. It merely
requires O(n2) comparison operations. If we were to compare
two integers, a and b using (for example) a Turing machine, we
would, in the general case, need to go over all their bits in order to find a
difference, so this operation is better described as an
O(log(min(|a|,|b|)))-time operation, rather than O(1).
One way to think about this is that the statement "Bubble sorting is an O(n2)-time operation" is simply false or, at best, a useful approximation. Another, perhaps more rewarding way to look at it is to recognize that computation complexity is a function of the computational model one works in, and that in most cases where we deal with complexity we implicitly consider a computational model where, unlike in the Turing-machine computational model, operations such as comparison of integers are atomic O(1)-time operations.
In mathematical riddles hidden assumptions are always problematic, for which reason I am describing here a complete computational model, composed entirely of operations that are almost invariably treated as atomic O(1)-time operations, which is the computational model this month's question refers to. The solution you are requested to provide is a description of an algorithm implementable in this model, which, when implemented in the model, will run in the desired complexity.
The model's operations are listed below. Where additional details are given in parentheses, they are meant to disambiguate the description. The operations supported by the model are:
Regarding flow control
As stated before, all of these operations are almost invariably assumed to be O(1), anyway, which makes this month's question all the more interesting. It is:
Design an algorithm for sorting n integers that takes O(n) time.
List of solvers:Hongcheng Zhu (1 December 18:33)
Gaoyuan Chen (2 December 00:21)
Yingjie Xu (3 December 03:45)
Omer Angel (3 December 07:24)
Sen Gu (4 December 20:03)
Bin Jin (5 December 00:41)
Dharmadeep Muppalla (8 December 21:59)
Yaron Gvili (19 December 17:10)
Marcos Simões (29 December 16:15)
Bojan Bašić (31 December 22:16)
Elegant solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.
The solution will be published at the end of the month.
Back to main page