## 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*) =

*n*

^{c}

*P*(log

_{2}

*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
*n*^{c}, where *c* =
log_{2}(*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.