Solution of a Divide-and-Conquer Maximin Recurrence
Zhiyuan Li, Edward M. Reingold · SIAM Journal on Computing · 1989
The solution of the divide-and-conquer recurrence\[ M(n)\mathop {\max }\limits_{1 \leqq k < n} (M(k) + M(n - k) + \min (f(k),f(n - k))) \]is found for a variety of functions f. Asymptotic bounds on $M(n)$ are found for arbitrary nondecreasing f, and the exact form of $M(n)$ is determined for f nondecreasing and weakly concave. As a corollary to the asymptotic bounds, it is shown that $M(n)$ remains linear even when f is almost linear. Among the exact forms determined: For $f(x) = \lfloor {\lg x} \rfloor $, the solution is $M(n) = (M(1) + 1)n - \lfloor {\lg n} \rfloor - u (n)$ where $ u (n)$ is the number of 1-bits in the binary representation of n. For $f(x) = \lfloor {\lg x} \rfloor $, the solution is $M(n) = (M(1) + 1)n - \lceil {\lg n} \rceil - 1$, while for $f(x) = \lceil {\lg (x + 1)} \rceil $, thesolution is $M(n) = (M(1) + 2)n - \lfloor {\lg n} \rfloor - u (n) - 1$.