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(nnlogn) for sequences of length n.

► The average complexity analysis for pairs of compatible sequences is presented.
► The analysis is done in two levels, so that an accurate estimate is achieved.
► We use tools of symbolic computation, such as holonomic functions and asymptotic analysis.
► An average complexity of O(nnlogn) for sequences of length n is derived.