Solution of a divide-and-conquer maximin recurrence. (English) Zbl 0692.68038
Summary: The solution of the divide-and-conquer recurrence
\[
M(n)=\max_{1\leq 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 -\nu (n)\) where \(\nu\) (n) is the number of 1-bits in the binary representation of n. For \(f(x)=\lceil lg x\rceil\), the solution is \(M(n)=(M(1)+1)n-\lceil lg n\rceil -1\), while for \(f(x)=\lceil lg(x+1)\rceil\), the solution is \(M(n)=(M(1)+2)n-\lfloor lg n\rfloor -\nu (n)-1\).
MSC:
68Q25 | Analysis of algorithms and problem complexity |
68R99 | Discrete mathematics in relation to computer science |
05A20 | Combinatorial inequalities |
26A12 | Rate of growth of functions, orders of infinity, slowly varying functions |