It takes a parameter k which determines the size of the array, which impacts both the quality of the estimates and the amount of memory used.
Assuming that the values i are integers in {0,...,m-1}, storing them requires ⌈log(m)⌉ bits.
Every item which occurs more than n/k times is guaranteed to appear in the output array.
The summaries (arrays) output by the algorithm are mergeable, in the sense that combining summaries of two streams s and r by adding their arrays keywise and then decrementing each counter in the resulting array until only k keys remain results in a summary of the same (or better) quality as compared to running the Misra-Gries algorithm over the concatenation of s with r. Let k=2 and the data stream be 1,4,5,4,4,5,4,4 (n=8,m=5).
The algorithm will then execute as follows(- signifies that no key is present): Output: 4