The Complexity of Computing the k-ary Composition of a Binary Associative Operator

Gerth Stølting Brodal
Sven Skyum

November 1996


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 tex2html_wrap_inline31 O(k) operations.

For the operator tex2html_wrap_inline35 we show in contrast that in the decision tree model the complexity is tex2html_wrap_inline37 O(k). Finally we show that the complexity of the corresponding on-line problem for the operator tex2html_wrap_inline35 is tex2html_wrap_inline43 O(k)

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.