This is a page of the former Algo team's web site. It won't be updated any longer.
 
Welcome! Research Topics People Publications Seminars Software On-Line Applications Jobs & Internships

ALGO logo  

Divide-and-conquer

Divide-and-conquer 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 divide-and-conquer 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

D&C logo
The number of 1 in the binary expansion of an integer is an example of a 2-rational sequence.

After an introduction to the divide-and-conquer strategy and the associated recurrences, we focus here on a particular class of sequences, 2-rational sequences, whose definition is recent and covers divide-and-conquer 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 2-rational 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