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).

Copyright notice

Copyright © 1996, BRICS, Department of Computer Science, Aarhus University. All rights reserved.

Online version

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

BIBT_EX entry

@techreport{brics-rs-96-42,
  author = "Gerth Stø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"
}