Talk:Master theorem (analysis of algorithms)

Origin of term

Where did the term "master theorem" originate? CLRS cites Bentley, Haken, and Saxe (1980) for the theorem, but the article by Bentley et al. does not use the term "master theorem". —Preceding unsigned comment added by 128.151.39.160 (talk) 17:02, 12 May 2011 (UTC)

Case2 skepticism

Looking into other sources about the issue, I find no reference for the exact stating of the "Case 2" given here.
Instead it appears to be described everywhere as the special case of (k=0).
Could it be that there is a mistake here? or is it that all other places are less general forms?
Having looked into Cormen's book, I see the same there: no 'k' mentioned in the second case's context.

Reference:
http://www.cs.concordia.ca/~chvatal/notes/master.pdf
http://www.columbia.edu/~cs2035/courses/csor4231.F03/recurrences.pdf
and many others.
Seftembr 23:32, 1 December 2006 (UTC)

---

Agreed... it was very confusing and I have never seen that either. I just made the change to the page.

Mpercy (talk) 09:55, 17 March 2008 (UTC)

---

The Case 2 showed here is not canon; it was supposed either to follow the CLRS' Master theorem, or should state it is instead a more general theorem. —Preceding unsigned comment added by 201.92.145.179 (talk) 00:12, 25 February 2009 (UTC)

The Case 2 showed here is exactly the one from the Goodrich-Tamassia book. I have added that reference to the article. —David Eppstein (talk) 00:42, 25 February 2009 (UTC)

Page Title Change: The Master Theorem

I believe there should be "The" in from of "Master theorem". In either case, can someone at least redirect it to here? As it currently stand, if you search "The Master Theorem", this page will actually NOT show up as a result!

24.222.8.32 17:33, 5 December 2006 (UTC)

I believe this is not true. I looked in the book quoted by the article and the word "The" is not capitalized in any references to it. — Preceding unsigned comment added by 184.58.117.18 (talk) 23:52, 16 October 2013 (UTC)

Excellent job

I have read many wikipedia pages that describe mathematical theorems. and many are very obtuse, and usually digress in many directions preventing the main idea from being conveyed. This article is of utmost excellence. And did a better job describing the theorem than my college book or professor. If any content is to be added, please make sure it is added below the existing content. The original content is very explanatory and the examples are very thourough and excellently explained. Some of the final answers where in a font rather small and hard to see on a 1024x768 resolution (please verify if this is a problem on other browsers) but otherwise, this is the most concise article on a mathmatical theorem i have read on wikipedia. It's greatness is in it's simplicity. Please do not dilute it, and keep up the good work! —The preceding unsigned comment was added by Jediborg (talk • contribs) 05:46, 20 February 2007 (UTC).

I completely agree with the above sentiments. I am learning this theorem from the very book that this article cites, yet this article does a MUCH BETTER JOB. Whoever wrote this is amazing and they did a great job.

[I am also using the book, my Master's class, and this article is so easy to understand. Definitely a terrific job here. Kudos, big time] — Preceding unsigned comment added by Joaquin.Ravelo (talk • contribs) 16:07, 6 September 2020 (UTC)

Ramanujan

The Ramanujan page links here; but I suspect for the wrong reason. Ramanujan had some sort of master theorem, but it involved Laplace transforms, as I recall. This one looks like it's from analysis of algorithms. The MacMahon one is a big thing from combinatorics.

Charles Matthews 15:50, 16 Apr 2004 (UTC)

You're right, Charles. Master theorem definitely needs a disambig. page. Giftlite

Relevance and Examples

This theorem is all well and good, but it just sits in space providing no reason why anyone would want to use it. It would be much better if an example or description of its relevance to the world, or mathematics was added. Centroyd

I feel the same way, studying it right now for a class!

Disagreed, the first sentence of the article gives exactly what you ask for. A.N. Yzelman 08:34, 21 June 2007 (UTC)

Category: Computer Languages

Also, does it really make sense to put this under 'Computer Languages' ?

It does not, but it seems to have been resolved already. A.N. Yzelman 08:34, 21 June 2007 (UTC)

a/b vs n/b

The discussion of a/b should be n/b, at least as given in Cormen, Leiserson and Rivest 1st Ed. p62. Terrycojones 09:25, 26 Oct 2004 (UTC)

Not sure which part you meant? Probably the error has already been corrected. A.N. Yzelman 08:34, 21 June 2007 (UTC)

Special Cases

I think that Special Cases should be discussed as well, as there are gaps between the cases. 66.130.236.213 19:13, 21 September 2006 (UTC)

Meet quality

I assume it needs to be rewritten. Some portion of this page is to be removed and some more descriptive portion is to be added. Nafsadh (talk) 20:21, 30 December 2007 (UTC)

Formal correctness

This writing is probably not correct (not only in this special case):

$T(n)=\Theta \left(n^{\log _{b}a}\right)$

Theta represents a set of functions and T(n) is only a special function of these it should rather be written

$T(n)\in \Theta \left(n^{\log _{b}a}\right)$

Though the first writing is commonly used, the second is mathematically correct and the first is not, because a set of functions(N->R) can not equal a single function(N->R)

95.223.140.220 (talk) 22:56, 4 July 2009 (UTC)

It is not for us here to promote nonstandard notation. "=Θ" is the standard notation for "has the same order of magnitude as", a relation between two functions rather than a membership relation between a function and a set. It is perfectly valid mathematically as long as one regards "=Θ" as being a single compound symbol rather than as two separate = and Θ symbols. The other notation is much less standard and should be avoided for that reason, logical though it may be. —David Eppstein (talk) 23:13, 4 July 2009 (UTC)

It is not very helpful that both versions are used inconsistently throughout the article. I'd be fine if everything was "=Θ" but it's not. I prefer the element version as it's more accurate semantically, though I agree that more people may use the other one for simplicity. Just be consistent. In any case, please don't call people pedantic when reverting changes. —Xiphoseer (talk) 14:32, 18 July 2017 (UTC)

Error in inadmissible example?

One example in section Inadmissible states:

"$T(n)=2T\left({\frac {n}{2}}\right)+{\frac {1}{n}}.$

There does not exist a c < 1 such that $2{\frac {2}{n}}\leq c{\frac {1}{n}}$."

However, the explanation is inconsistent with the description of Case 3 of the master theorem.

I suspect this was just a simple inversion typo and that the explanation should read:

"There does not exist a c < 1 such that $2{\frac {n}{2}}\leq c{\frac {1}{n}}$."

What do you think?

smt (talk) 23:35, 3 November 2009 (UTC)

Inadmissible equation?

Inadmissible equations says "... cannot be solved using the master theorem".

Isn´t it the case that you can solve
$T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}$
by the substitution $S(n)={\frac {T(n)}{2^{2n}}}$ to get
$T(n)/2^{2n}=T\left({\frac {n}{2}}\right)/2^{n}+({\frac {n}{4}})^{n}$ or equally $S(n)=S\left({\frac {n}{2}}\right)+({\frac {n}{4}})^{n}$
and, with Master Theorem case 3 under the condition
$(n/8)^{n/2}\leq c\cdot (n/4)^{n}$
which is true almost everywhere for arbitrary choosen constant $0<c<1$, you get
$S(n)=\Theta \left(({\frac {n}{4}})^{n}\right)$.
This leads to the asymptotic term $T(n)=\Theta (n^{n})$ by using the Master Theorem I think. Joerg Bader (talk) 00:33, 18 February 2011 (UTC)

Case 1 formal note

If f=0, then f is obviously O-big of anything. It is reasonable to expect that Theta=const=0 is also possible as a solution, but the theorem states that it can't be the case. Maybe it is missing somewhere the requirement that f>0? 80.237.26.14 (talk) 15:25, 27 July 2011 (UTC)

Name of article

The name "Master theorem" for this article is silly. It is the "master theorem" for solving a certain class of recurrences that are found in algorithmic analysis. But there are other master theorems in other fields. Just because a lot of writers of wikipedia have a computer science background, and therefore are likely to be more familiar with that usage, doesn't mean that this is a good title. I would suggest something like Master theorem (recurrences) or Master theorem (analysis of algorithms). --Macrakis (talk) 13:07, 27 April 2017 (UTC)

See WP:PARENDIS — disambiguation should be used only when a title is actually ambiguous. —David Eppstein (talk) 15:42, 27 April 2017 (UTC)

It is actually ambiguous. There are things called "master theorems" in combinatorics and analysis. Just because they also have alternative names doesn't make this one the definitive "master theorem". --Macrakis (talk) 22:29, 28 April 2017 (UTC)

I agree in estimating Master theorem without any qualifier as a silly nomenclature, which a -to me- good encyclopedia should avoid, even when the sages of a particular field request their dominance. Purgy (talk) 09:15, 12 June 2017 (UTC)

It seems clear that this is the "Master theorem" for recurrences found in the analysis of algorithms, but that this name is not used outside that subfield. It doesn't even seem to be used in the mathematical study of recurrences in general.

For example, in the first 20 results for the search "master theorem" on Google Scholar, only 4 are about this theorem. And of those 4, 3 explicitly call it "a" "master theorem for divide-and-conquer recurrences". That is, not only do they qualify it by its field of application, they don't call it "the" master theorem, but just "a" master theorem.

So, just a final check:

a) can we find any uses of the term "master theorem" outside the analysis of algorithms that refer to this particular theorem?

b) any objections to the title Master theorem (divide and conquer recurrences)?

--Macrakis (talk) 09:26, 13 June 2017 (UTC)

I agree with the criticisms of the name "master theorem." Master theorem (divide and conquer recurrences) is also terrible, though -- unguessable, unsearchable, and a horrible mouthful. "Master theorem (algorithms)" or "Master theorem (analysis of algorithms)" would be better (though the latter is also a pretty bad mouthful). --JBL (talk) 15:02, 13 June 2017 (UTC)

Agreed that "Master theorem (divide and conquer recurrences)" is clumsy, but that is what is called in the literature, which is what we're supposed to use to guide us.

• "A general method and a master theorem for divide-and-conquer recurrences with applications", RM Verma - Journal of Algorithms, 1994
• "An improved master theorem for divide-and-conquer recurrences", S Roura - Automata, Languages and Programming, 1997
• "A master theorem for discrete divide and conquer recurrences", M Drmota, W Szpankowski - Journal of the ACM (JACM), 2013

It is unguessable, I agree. Except that the "search Wikipedia" box has typeahead, so you should see the suggestion as soon as you type "Master t", just as you do today.

I don't think it's unsearchable. Both Google search and Wikipedia search already return the Master theorem article in position #1. with (e.g.) the search [algorithm recurrence theorem]

--Macrakis (talk) 17:58, 14 June 2017 (UTC)

OK, I have moved the article and updated links to it. Most of them now look like master theorem for divide-and-conquer recurrences, because that is what makes sense in context. I think that would actually have been a better name for the article, but that didn't seem to appeal to other editors.... --Macrakis (talk) 21:30, 7 October 2017 (UTC)

Proposed changes June 11th

I am taking the initiative to start a discussion here, because user David Eppstein has provably started an edit war in bad faith (as evidenced by his revision comments, "pedantic notation unused by anyone except pedants, not accidental", as well as his history of other vitriolic revision comments towards others in the past, in this very article, which can be noted in the history). I have spent the better part of a day hoping to contribute to the pedagogy of this article and to, after significant amounts of consideration and revision, distill the salient and most important parts of the article into a more concise, elegant, and understandable form, especially for students new to the art. I have also spent the better part of a day trying to improve the article by creating a custom-made table.Ninjagecko (talk) 06:11, 12 June 2017 (UTC)

User David Eppstein has brashly reverted parts he did not even object to or discuss (likely by accident at first), and continues to do so, and has not edited, while I attempted to edit things to address his specific concerns. Below I compare the two additions to the article, and people unaffiliated with either of us should feel free to comment to reach a consensus:Ninjagecko (talk) 06:11, 12 June 2017 (UTC)

Proposed changes

This is a snapshot of the Generic Form section, after my proposed changes: https://en.wikipedia.org/w/index.php?title=Master_theorem&oldid=785156913#Generic_Form Ninjagecko (talk) 06:11, 12 June 2017 (UTC)

Prior state

This is a snapshot of the Generic Form section, before my proposed changes, to which the article is being reverted to: https://en.wikipedia.org/w/index.php?title=Master_theorem&oldid=784218527#Generic_form Ninjagecko (talk) 06:11, 12 June 2017 (UTC)

Improvements

I made the changes to help address some shortcomings with this article: Ninjagecko (talk) 06:11, 12 June 2017 (UTC)

• The examples were unavoidably verbose, and while important, were intermingling too much with the definition to the point that one would have trouble comparing and contrasting the three regimes without wading through lots of text. Ninjagecko (talk) 06:11, 12 June 2017 (UTC)
• I felt the three cases were not sufficiently stated as a spectrum vis-a-vis each other. The tabular layout, specifically the Description column, clarifies their relation. It also clarifies the log terms, and uses similar language to highlight symmetry in the regimes (such as how each regime is dominated by various parts of the recursion tree). Ninjagecko (talk) 06:11, 12 June 2017 (UTC)
• The quantity $log_{b}a$ should be noted appears mainly as an exponent, and the associated polynomial should be stressed as an important quantity: the regime is determined by how the $f(x)$ term asymptotically relates to it, which the article did not yet properly show. Ninjagecko (talk) 06:11, 12 June 2017 (UTC)
• Added numerous clarifications. Ninjagecko (talk) 06:11, 12 June 2017 (UTC)
• Added $\epsilon$ because it is a simpler definition (but as with everything here, open to discussion). Ninjagecko (talk) 06:11, 12 June 2017 (UTC)
• Added symmetry of examples, that was stressed by the tabular layout. Ninjagecko (talk) 06:11, 12 June 2017 (UTC)
• Added a more verbose formula which instantly clarifies the difference between $a$ and $b$ on sight, and that $f(x)$ is a term derived from work splitting and recombining. I assume here that mathematicians and computer scientists might have some innate biases here, but we should feel free to discuss. Ninjagecko (talk) 06:11, 12 June 2017 (UTC)

Yes, there is still room for improvement after these improvements, but I believe they're a step in the right direction. Ninjagecko (talk) 06:11, 12 June 2017 (UTC)

Furthermore, I added a table. I felt a lookup table for very common values of a,b in $log_{b}a$, with symmetry, would help illustrate the structure of common asymptotic bounds that the Master Theorem spits out. I feel such tables add an intuitive understanding of things. They are commonly seen in many computer science articles, in which I also feel they (there) add significantly to a quick, intuitive understanding of things. The coloring is automatically calculated such that the same exponents are the same color, and the column that states divergence is an important part of highlighting what happens intuitively when b=1. The table sizes were chosen to fit comfortably on most resolutions (though if someone has specialty in wikipedia mobile, they should feel free to chime in). The table was reverted as being "gaudy", but I feel color is acceptable when used for things like plots and graphs if it adds value (in this case, equal things have the same color, and the scale is a log scale). Ninjagecko (talk) 06:11, 12 June 2017 (UTC)

I hope that any objectors can make their full objections clear here rather than reverting, and that together we can work to improve the article. Thank you. Ninjagecko (talk) 06:11, 12 June 2017 (UTC)

Some specific things I object to in your rewrite:

• Ignoring the manual of style for capitalization ("Generic form" vs "Generic Form"; "The Master Theorem"
• Ignoring the manual of style re use of first person ("The Master Theorem sometimes gives us")
• Incorrect use of mathematics formatting (hint: in your coding <math>work(n)</math>, you are juxtaposing four individual variable names w, o, r, and k)
• Anthropomorphic fallacy ("The Master Theorem says" ... no, it doesn't, the action of speaking is not something a theorem can do)
• Sesquipedlian writing-around-the-point instead of simple direct language ("Whenever we have a recurrence of this form, we can consider it as occurring in one of three regimes, based on how the work to split/recombine the problem relates to the special quantity")
• Ridiculous set-theoretic notation that does not work to describe how O-notation is actually used ($f(x)\in O(n^{c})$). We should not be pushing idiosyncratic notations here (WP:SOAPBOX) and this notation is objectively wrong (doesn't work for situations where the O-notation is used for only part of an expression).

And that's just in your latest cut-down diff where you didn't also include the 50000 bytes of colorization and commented-out Python code for colorization (?) that added nothing of value to the article. Look, you have been on Wikipedia for over 10 years; how have you managed not to pick up even the basic points of the manual of style? —David Eppstein (talk) 06:17, 12 June 2017 (UTC)

Discussion

• Slightly violating the WP:MOS, even after editing for decades on WP, should not disqualify any edits, but attract some gnomes to rectify certain violations of capitalizing, inappropriate direct addressing of readers, projecting anthropomorphism to theorems (is it allowed to have one such to state a proposition?), and other nitpicking like non-italicizing op-names.
• In a similar effort, those who feel themselves comfortable in their elaborate use of the English language as it is correctly spoken/written in WP, should be able to save the half step in sesquipedaling.
• Personally, I would like to avoid writing about some notation others use to be ridiculous, at least as long as the intention is reconstructible. Considering that even abusive notation is in heavy use, I suggest to check if editing out the ridicule improves the article.
• I consider color to be a design element, not available to Gutenberg and his first successors, and still somewhat rare within books not intended for infantile readership, the good use of which greatly enhances intelligibility of complex content.
• Are there any non-formal objections to the proposed content?

Look, how could one rank form over function? Purgy (talk) 10:09, 12 June 2017 (UTC)

I can't even get to what has changed in the function because the form is unreadable. And that includes being written in unreadable English, not just minor details of capitalization. —David Eppstein (talk) 14:38, 12 June 2017 (UTC)

Also, the new text "Whenever we have a recurrence of this form, we can consider it as occurring in one of three regimes" is objectively false. There are plenty of recurrences of this form that do not fall under any case of the theorem. —David Eppstein (talk) 06:18, 13 June 2017 (UTC)

I think that tables can be a good way of conveying some kinds of information, but in the present case every single entry in the table is itself a block of text -- there is no advantage created, you still have to read every single block of text to understand what it's saying, and reading small cramped blocks of text is harder than reading paragraphs. I do not think the table is an improvement. (By contrast, the smaller table at the bottom of the article shows a place where a tabular presentation can allow for easy comparison by eye.) The redundant words-ful formulas are also terrible, they are helpful only if you already know what they mean -- the cleaner formula with a sentence explaining how to interpret its terms is much better. I have not made any attempt to evaluate any smaller-scale edits. --JBL (talk) 14:57, 13 June 2017 (UTC)

P.S. Whatever way this gets resolved, the "See also" section is in a very weird place and will need to be relocated. --JBL (talk) 15:02, 13 June 2017 (UTC)

I have tried to work in some of your feedback about the verbosity of the regime table, and the textual equation, and some other concerns of David Eppstein's in the following edit. https://en.wikipedia.org/w/index.php?title=Master_theorem&oldid=785547309 Ninjagecko (talk) 04:46, 14 June 2017 (UTC)

Binary tree traversal

How is binary tree traversal complexity C(n) = 2 C(n/2) + O(1)? Is the tree assumed to be almost complete to have both sides of size n/2? — Preceding unsigned comment added by Quentin Fortier (talk • contribs) 09:22, 17 September 2017 (UTC)

Small note on usage of k

In the pseudocode we have the statement: if n < some constant k. This can be confused with the k in case examples under the section of Generic form when glancing through the article. Dizqar (talk) 15:04, 1 May 2021 (UTC)

Minor glitch in use of Big Theta

This phrase does not make sense: "T(n) = Theta(1) when n is less than some bound kappa".

If n is bounded then asymptotic stuff about a function of n don't make sense.

Just say "T(n) is bounded" instead of "T(n) = Theta(1)". 2601:985:4380:C00:980B:EA88:5DB3:A164 (talk) 15:08, 2 November 2022 (UTC)