Talk:Master theorem (analysis of algorithms)

Question about merge function in Master theorem

Someone just asked the following question in the article, so i copy it to the talkpage:

Can anyone give a function which satisfies,

$f(n)\in \Omega \left(n^{\log _{b}a+\epsilon }\right)$ for a $\epsilon >0$

but it does not satisfy,

$af\left({\frac {n}{b}}\right)\leq cf(n)$ for a $c<1$ and sufficiently large n

--Regnaron 05:28, 4 October 2006 (UTC)

Wikipedia is not for answering homework or anything. Also, I believe that an answer to that question is actually given in a certain resource linked to in this discussion page; a little looking around was too much work for the questioner?

A.N. Yzelman 08:26, 21 June 2007 (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)

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.

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)

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)