An asymptotic theory for recurrence relations based on minimization and maximization

✍ Scribed by Hsien-Kuei Hwang; Tsung-Hsi Tsai

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 242 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00066-x

✦ Synopsis

We derive asymptotic approximations for the sequence f(n) deÿned recursively by f(n) = min16j¡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) = max16j¡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.