 This algorithm is optimal under the decision tree model of computation.The algorithm is a generalization of the one for a special case of "k"=2 (the Boyer–Moore majority vote algorithm), which had a rather convoluted history of publication.The above algorithms rely only on the test of identity of the elements.