5
$\begingroup$

In all of the classes I've had on algorithms, and the books I've seen that talk about the master theorem, none of them mention where it came from, which is pretty odd. Certainly, it didn't just kind of spring into existence, and it's not obvious either. So, who came up with it, and when? And why isn't it called so-and-so's theorem?

  • 0
    Are you sure it is not really *the MASTER theorem*, from a paper of Morsi, Astem, Stein, Tamil, Erret, and Rivest ??? :)2012-12-13

2 Answers 2

4

See: http://en.wikipedia.org/wiki/Master_theorem

It has references to answer your question ( Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, in which it is both introduced and proved).

Here is a paper on it: http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf

Regards -A

  • 0
    Nice links! ;-)2013-04-13
2

Refer to A General Method for Solving Divide-and-Conquer Recurrences by Jon Louis Bentley, Dorothea Haken, James B. Saxe published in 1980.

http://dl.acm.org/citation.cfm?id=1008865

  • 0
    I've looked in my copy of CLRS. In the chapter 4 notes, they state that "The master method is adapted from Bentley, Haken, and Saxe [44]".2012-12-13