On the average complexity for the verification of compatible sequences
The average complexity analysis for a formalism pertaining pairs of compatible sequences is presented. The analysis is done in two levels, so that an accurate estimate is achieved. The way of separating the candidate pairs into suitable classes of ternary sequences is interesting, allowing the use of fundamental tools of symbolic computation, such as holonomic functions and asymptotic analysis to derive an average complexity of O(n root n log n) for sequences of length n. (C) 2011 Elsevier B.V. All rights reserved.
complexity sequences symbolic computation periodic autocorrelation function non-periodic autocorrelation function algorithms average-case analysis