Computational complexity of the algorithm creating hypermetric rhythmic hypotheses

Abstract

This study presents the algorithm creating rhythmic hypotheses worked out by the authors, and then addresses the problem of determining its computational complexity. A short review of rhythm extraction methods is presented, first. Then, three phases of the algorithm engineered by the authors, namely creating periods, creating simplified hypotheses and creating full hypotheses are examined. The analyses of computational complexity of the method proposed assume that the engineered method is expected to rank rhythmic hypotheses formed of three rhythmic levels above meter. This proved to be sufficient for providing automatic drum accompaniment for a given melody without delay.