Using your Head is Permitted

December 2008 riddle

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 integers

  • The four basic arithmetic operations (addition, subtraction, multiplication and division) as well as modulo-taking are all O(1).
  • The bitwise operations AND, OR and NOT are O(1). (We use the standard 2's-complement representation of integers for the bitwise operations, so "14 AND 13 = 12" and "14 AND -13 = 2".)
  • Comparisons (less than, greater than, equals to) are all O(1).
  • Shift-left and shift-right by n bits, for any integer n, are O(1). (The result of this is the same as multiplication/division by 2n.)

Regarding arrays

  • Allocating/deallocating an array of any size is O(1)-time. (An array stores a single integer in each of its cells. Cell indices are integers. Arrays start off as non-initialized, meaning that if an array cell is read before it was ever written to, the value read may be any integer. Arrays can not change their sizes once allocated.)
  • Accessing a given array position for either reading or writing is O(1). (Accessing an array position outside the array bounds [either by use of an index with a negative value or one larger than the array's maximum] leads to undefined results. Array indices are zero based.)
  • Input and output of the program are special cases of array reading and array writing (respectively), and follow the same complexity. (Also: integer variables are special cases of arrays of size 1. Integer constants [i.e. program literals] are like variables, but they are, unlike regular arrays, initialized to their constant value and cannot be given new values.)

Regarding flow control

  • Jumps are performed in O(1) time.
  • Conditional jumps are perfomed in O(1) time, in addition to the time it takes to evaluate the condition.

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


To solution

Back to main page