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

  • Gerth Stølting Brodal
  • Sven Skyum

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 3(k−1)/ (k+1)n − O(k) operations.
For the operator max we show in contrast that in the decision
tree model the complexity is (1+ Theta(1/sqrt(k)) n − O(k).

Finally we show that the complexity of the corresponding on-line problem for the operator max is (2 − 1/(k−1)) n − O(k).

Published
1996-06-12
How to Cite
Brodal, G., & Skyum, S. (1996). The Complexity of Computing the k-ary Composition of a Binary Associative Operator. BRICS Report Series, 3(42). https://doi.org/10.7146/brics.v3i42.20024