Welcome!  Research Topics  People  Publications  Seminars  Software  OnLine Applications  Jobs & Internships 
Divideandconquer 
Divideandconquer  Maple  Publications  Address  Version française  GoSaZi95  DuGo97 
The political proverb divide ut imperes is now a fundamental strategy in computer science; it appears in the multiplication of polynomials as well as in sorting algorithms or in the search for convex hulls. In each case a natural concept of size leads us to consider the cost of the employed algorithm; thus divideandconquer sequences appears. They are defined by recurrences in which the cost for a data of a certain size depends on the cost for a data of half size. The quality of the algorithms under consideration depends on the asymptotic behavior of such sequences and the study of this behavior thus proves to be an essential problem in this context.
Table of contents 

After an introduction to the divideandconquer strategy and the associated recurrences, we focus here on a particular class of sequences, 2rational sequences, whose definition is recent and covers divideandconquer recurrences occurring in computer science. These sequences have a rich algebraic structure depending on the binary expansion of integers and on the rational series of formal language theory. In particular a basic concept is that of a linear representation; it generalizes the classical link between powers of a matrix and linear recurrence with constant coefficients. An easy consequence of this concept is the polynomial type behavior of 2rational complex sequences.
To perform the asymptotic study of these sequences one can apply elementary techniques on simple examples, but to obtain deep results it is necessary to resort to sophisticated methods coming from analytic number theory. In the manageable cases, the application of Perron's formula to the Dirichlet series associated with the sequence makes it possible, , to emphasize subtle oscillations in logarithmic scale.
Next page:  A fundamental idea 