Jon Louis Bentley
Dorothea Haken
Abstract
The approximate complexity of divide-and-conquer algorithms is often described by recurrence relations of the formT(n) = kT(n/c) + f(n).The only well-defined method currently used for solving such recurrences consists of solution tables for fixed functions f and varying k and c. In this note we describe a unifying method for solving these recurrences that is both general in applicability and easy to apply. This method is appropriate both as a classroom technique and as a tool for practicing algorithm designers.
- Aho, A. V., J. E. Hopcroft and J. D. Ullman {1974}. The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass. Google Scholar
Digital Library
- Bentley, J. L. and M. I. Shamos {1976}. "Divide and conquer in multidimensional space", Proceedings of the Eighth Symposium on the Theory of Computing, ACM, May 1976, pp. 220--230. Google ScholarDigital Library
- Borodin, A. and I. Munro {1975}. The Computational Complexity of Algebraic and Numeric Problems, American Elsevier, New York, N.Y.Google Scholar
- Ford, L. and S. Johnson {1959}. "A tournament problem", American Mathematical Monthly 66, pp. 391--395.Google ScholarCross Ref
- Keller, K. {1980}. "Computation cost functions for divide-and-conquer algorithms", to appear in Journal of Undergraduate Mathematics.Google Scholar
- Knuth, D. E. {1973}. The Art of Computer Programming, volume 3: Sorting and Searching, Addison-Wesley, Reading, Mass. Google ScholarDigital Library
- Kung, H. T. {1973}. A New Upper Bound on the Complexity of Derivative Evaluation, Carnegie-Mellon University Computer Science Report, September 1973.Google Scholar
- Kung, H. T., F. Luccio and F. P. Preparata {1975}. "On finding the maxima of a set of vectors", JACM 22, 4, October 1975, pp. 469--476. Google ScholarDigital Library
- Liu, C. L. {1977}. Elements of Discrete Mathematics, McGraw-Hill, New York, N. Y. Google ScholarDigital Library
- Manacher, G. K. {1977}. "The Ford-Johnson sorting algorithm is not optimal", Proceedings of the Fifteenth Annual Allerton Conference on Communications, Control and Computing, September 1977, pp. 390--397.Google Scholar
- Pan, V. Ya. {1978}. "An introduction to the trilinear technique of aggregating, uniting and cancelling and applications of the technique for constructing fast algorithms for matrix operations", Proceedings of the Nineteenth Annual Symposium on the Foundations of Computer Science, IEEE, 1978.Google Scholar
- Stanat, D. F. and D. F. McAllister {1977}. Discrete Mathematics in computer Science, Prentice-Hall, Englewood Cliffs, N. J. Google ScholarDigital Library
- Strassen, V. {1969}. "Gaussian elimination is not optimal", Numerische Mathematik 13, pp. 354--356.Google ScholarDigital Library
Index Terms
- A general method for solving divide-and-conquer recurrences
Recommendations
A Master Theorem for Discrete Divide and Conquer Recurrences
Divide-and-conquer recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences, namely for some known sequence an and given bj, bj, pj and δj, δj, present some challenges. The discrete nature of ...
A master theorem for discrete divide and conquer recurrences
SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithmsDivide-and-conquer recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences, namely
[EQUATION]
for some known sequence an and given bj, pj and δj, present some challenges. The discrete nature of ...
A Gröbner-basis theory for divide-and-conquer recurrences
ISSAC '20: Proceedings of the 45th International Symposium on Symbolic and Algebraic ComputationWe introduce a variety of noncommutative polynomials that represent divide-and-conquer recurrence systems. Our setting involves at the same time variables that behave like words in purely noncommutative algebras and variables governed by commutation ...
Comments