Minmax recurrences in analysis of algorithms

摘要

The solution of a challenging minmax recurrence relation is presented. This relation is derived from a model of parallel divide-and-conquer computations that incorporates the unavoidable and significant parallel processing overheads. The minmax recurrence is solved by characterizing the properties of the optimal partition sizes. It is shown that the optimal partition size, given a problem size n, is nontrivial and very different from the ad hoc n/2 value taken conventionally. It is also shown that the complexity of the algorithm reduces from O(n) to O(/spl radic) by choosing the optimal partition size instead of the equal partition size size at every stage of the recursion. The authors also survey some of the existing theory of minmax recurrence relations. They mention three interesting recurrences, how they are derived in the analysis of algorithms, and how they are solved by various authors.