Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Lundi 5 Décembre 2016

Periodic oscillations of divide-and-conquer recurrences dividing at half

par Hsien-Kuei Hwang (Academia Sinica, Taiwan)

Divide-and-conquer recurrences of the form

f(n) = a f(floor(n/2)) + b f(ceiling(n/2)) + g(n) for n >1

with g(n) and f(1) given, appear very frequently in the analysis of algorithms. While most previous methods and results focus on simpler crude approximation to the solution, we show that the solution satisfies always the simple identity

f(n) = nc P(log2 n) - Q(n)

under an optimum (iff) condition on g(n).

This form is not only an identity but also an asymptotic expansion because Q(n) is of a smaller order than nc, where c = log2(a+b). Explicit forms for the continuous periodic function P are provided. We show how our results can be easily applied to many dozens of concrete examples collected from the literature, and how they can be extended in various directions. Our method of proof is surprisingly simple and elementary, but leads to the strongest types of results for all examples to which our theory applies.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr