Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
According to wikipedia it was introduced in CLRS. –  JSchlather Dec 13 '12 at 21:42
    
Are you sure it is not really the MASTER theorem, from a paper of Morsi, Astem, Stein, Tamil, Erret, and Rivest ??? :) –  GEdgar Dec 13 '12 at 22:59
add comment

2 Answers

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

share|improve this answer
1  
Both of those articles describe and prove the master theorem, but as far as I can tell skimming them, neither one of them answers my question, which is about the history of the master theorem. I didn't see anything about that in the wikipedia references either. –  limp_chimp Dec 13 '12 at 21:44
    
See the addition I made to the answer (it was introduced and proved). –  Amzoti Dec 13 '12 at 21:45
1  
Really, it was introduced in a textbook? Not in a journal?I find that hard to believe; for one thing, a textbook seems like an odd place to introduce results of research. For another, it seems hard to believe that a result so fundamental to the study of algorithms wouldn't have been invented by the time a major textbook such as CLRS was being written. But if that's indeed the origin of the theorem, then I suppose I stand corrected. –  limp_chimp Dec 13 '12 at 21:47
    
Great point - I am probably mistaken on that point. However, we would have to look in the book for the references, or try to look at things like: A General Method for Solving Divide-and-Conquer Recurrences by Jon Louis Bentley, Dorothea Haken, James B. Saxe (my guess is that it is referenced in the book), so you are correct. Just a guess though on my part. –  Amzoti Dec 13 '12 at 21:50
    
Nice links! ;-) –  amWhy Apr 13 '13 at 0:23
add comment

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

share|improve this answer
    
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]". –  JSchlather Dec 13 '12 at 23:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.