Abstract:
Exact and asymptotic solutions of the divide-and-conquer recurrence
f(n) = a f(floor(n/2)) + b f(ceiling(n/2)) + g(n)
are derived and examined from the perspective of periodic oscillations. Optimum conditions are derived for the continuity of the underlying periodic functions. The results are applied to more than 500 examples
in computer algorithms, arithmetic functions, combinatorial sequences, cellular automata, etc.
This talk is based on joint work with Svante Janson and Tsung-Hsi Tsai.