Abstract:
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)
Available as PostScript, PDF, DVI.