An asymptotic theory for recurrence relations based on minimization and maximization
We derive asymptotic approximations for the sequence f(n) defined recursively by f(n) = min(1 less than or equal to j < n) {f(j) f(n-j)} + g(n), when the asymptotic behavior of g(n) is known. Our tools are general enough and applicable to another sequence F(n) = max(1 less than or equal to j < n) {F(j) + F(n - j) + min{g(j), g(n - j)}}, also frequently encountered in divide-and-conquer problems. Applications of our results to algorithms, group testing, dichotomous search, etc. are discussed. (C) 2002 Elsevier Science B.V. All rights reserved.
recurrence relations divide-and-conquer slowly varying functions power-of-two rules optimal algorithms