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

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* (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 *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.