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

## Gerth Stølting Brodal and Sven Skyum

Technical Report, BRICS-RS-96-42, BRICS, Department of Computer Science, Aarhus University, 15 pages, November 1996.

## 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+Θ(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).

Online version

brics-rs-96-42.pdf (240 Kb)

BIBTEX entry

@techreport{brics-rs-96-42,
author = "Gerth St{\o}lting Brodal and Sven Skyum",
institution = "BRICS, Department of Computer Science, Aarhus University",
issn = "0909-0878",
month = "November",
number = "BRICS-RS-96-42",
pages = "15",
title = "The Complexity of Computing the $k$-ary Composition of a Binary Associative Operator",
year = "1996"
}