The Complexity of Computing the k-ary Composition of a Binary
Gerth Stølting Brodal
We show that the problem of computing all contiguous k-ary compositions of a sequence of n values under an associative and commutative operator requires O(k) operations.
For the operator we show in contrast that in the decision tree model the complexity is O(k). Finally we show that the complexity of the corresponding on-line problem for the operator is O(k)