Tighter Bounds on the Solution of a Divide-and-Conquer Maximin Recurrence

✍ Scribed by Biing-Feng Wang

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 207 KB
• Volume: 23
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0839

✦ Synopsis

Let M n be defined by the recurrence

where f is an arbitrary nondecreasing function and M 1 is given. The recurrence Ž . M n is a divide-and-conquer maximin recurrence, which occurs in a variety of Ž . problems in the analysis of algorithms. In this paper, a new upper bound on M n is first derived. The derived bound is smaller than the one proposed previously by Ž . Li and Reingold. It is at most two times the exact solution of M n . Using the Ž . Ž . Ž . bound, we further show that M n F 2 E n , where E n is defined by the Ž . Ž? @. Žu v. Ž? @. recurrence E n s E nr2 q E nr2 q f nr2 . From this result, we can conclude that a divide-and-conquer algorithm whose time complexity is expressed as Ž . M n is as efficient as a divide-and-conquer algorithm whose time complexity is Ž . expressed as E n .