I propose a simple polynomial algorithm for the following problem. Given $m$ integers each one stored on $n$ bits, output the integer that appears the most often.
- Reserve a memory area with $2^n$ slots/registers/locations/cells, each cell being long enough to store the number $m$. This requires constant time because we do not initialize/touch the cells. If you agree with this, skip to step 2. Otherwise, check the following four points.
- One could easily be tempted to read "reserve a memory area" as "allocate a memory area". Actually, the memory allocation operation is an invention/complication of real multi-tasking machines where programs can "fight" for memory. If I consider some (Random Access Machine) RAM machine that only knows running my algorithm, I can state that the algorithm can simply use the whole memory. Thus, it is enough to reserve (read "put aside" not "allocate") the first $2^n$ cells for a an array with $2^n$ elements. The next memory cells are simply used for other variables.
- To be more precise, I consider running my algorithm on a RAM-TM (Random Access Memory-Turing Machine) that is multi-tape TM with a memory and an index tape. Given a number written on the index tape, the RAM-TM takes constant time to move the head of the memory tape to the location indicated on the index tape. We also allow the RAM-TM to have a few other tapes for easily doing arithmetics. The RAM-TM has no notion of memory allocation. This seems to be a simplification of the various (Transdichotomous or word) RAM machines out there.
- Even if I must confess I do not really know the exact technical details of all theoretical machines RAM (or RASP), it is possible to work with an exponentially-large memory area and yet use only a polynomially large number of cells and my algorithm is not the first doing this. This also happens in the binary search algorithm over a sorted array: $n$ cells but only $O(log(n))$ time complexity. This scientific paper introduced a data structure that uses a large memory area but has constant time access, see also the answer of zotachidil to this question. My algorithm could work with this data structure instead of explicitly reserving space.
- see Ps 1.
- Go through the $m$ numbers in the input and for each one of them $x$ assign $[x]=0$, where $[x]$ is the memory slot/location number $x$ in the above reserved memory area.
- Go through the $m$ numbers in the input and for each one of them $x$ assign $[x]=[x]+1$.
- Take the first number $x$ in the input and assign $outVal=x$ and $maxFreq=[x]$.
- Scan again the $m$ numbers and for each number $x$ perform: if $[x]>maxFreq$, set $outVal=x$ and $maxFreq=[x]$.
- Output $outVal$.
The algorithm has time complexity $O(mn)$ assuming $n\hskip 0.7mm \not \hskip -0.7mm \ll m$ at least on the RAM-TM (see ps 2.), i.e., linear. It is certainly not the only algorithm to solve the problem, but I do not know any other linear algorithm using polynomial memory.
However, the big problem is that the algorithm would require exponential time in a Turing machine, no? Does this contradict one of the Extended/Complexity-Theoretic Church–Turing Theses? The section "Variations" of the Wikipedia article on the Church–Turing thesis states that "polynomial-time overhead and constant-space overhead could be simultaneously achieved for a simulation of a Random Access Machine on a Turing machine [55]", where [55] is "C. Slot, P. van Emde Boas, On tape versus core: an application of space efficient perfect hash functions to the invariance of space, STOC, December 1984". Something seems inconsistent. Any help would be greatly appreciated.
ps 1. A real-machine argument for the fact one can allocate $O(2^n)$ bits in constant time. Notice I did not say the $2^n$ cells are initialized to some zero values. In a programming language like C this should be achieved by an instruction malloc instead of calloc. In my comment to D.W.'s answer, I provide a reference for a real-life memory allocator that "performs the allocation/deallocation in constant time". However, D.W. seem to reject this argument, claiming the above "constant time" is calculated by ignoring the fact that we can have $n\to \infty$ since in practice $n$ does no go to $\infty$, if I understood the response. As for me, it is hard to believe this "constant time" is actually $O(2^n)$, constant time is really far from $O(2^n)$. I would be surprised to see such large approximations in a paper published by Real-Time Systems.
ps 2. Not really essential, but a technical edit: because of Step 5, the complexity of the algorithm should be $O(nm+m\cdot log(m))$ on a RAM-TM and not $O(nm)$, which is relevant only if $n$ is very very small compared to $m$.