TY - JOUR
AU - Gerth Brodal
AU - Sven Skyum
PY - 1996/06/12
Y2 - 2020/12/04
TI - The Complexity of Computing the k-ary Composition of a Binary Associative Operator
JF - BRICS Report Series
JA - BRICS
VL - 3
IS - 42
SE - Articles
DO - 10.7146/brics.v3i42.20024
UR - https://tidsskrift.dk/brics/article/view/20024
AB - 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 decisiontree 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).
ER -