Talk:Proof of O(log*n) time complexity of union–find

Formatting makeover

The formatting of this page (especially of the mathematics) was pretty cruddy, so I went through and did what I could, fixing up some grammar while I was at it. I haven't actually read the article yet, so it's quite possible I goofed something up by misinterpreting it.Dfeuer (talk) 05:27, 6 July 2012 (UTC)

Lemma 3

Lemma three isn't explicitly mentioned anywhere after its statement. Dfeuer (talk) 06:14, 6 July 2012 (UTC)

Lemma 2 wrong?

The proof of Lemma 2 only considers "Makeset" and "Union", but not "Find"; and indeed path compression will cause a violation of the claim.

This raises (again) the following question: — Preceding unsigned comment added by Martin Ziegler (talk • contribs) 09:33, 4 April 2018 (UTC)

Original research?

Whose proof is this? If it was previously published, is there a copyright problem? If not, is it prohibited as original research? Dfeuer (talk) 09:14, 7 July 2012 (UTC)

This is about the most lucid and simple proof I have seen of the (non-optimal) fact that Union-Find algs have amortized runtime bounded by O(log* n). I plan to use this in my teaching notes on the topic.

Chris Lacher — Preceding unsigned comment added by 69.254.177.155 (talk) 17:13, 15 December 2013 (UTC)

Should this be an Article?

Proofs do not normally get their own articles. At best, this should be merged with http://en.wikipedia.org/wiki/Disjoint-set_data_structure. At worst, it should be removed as original research.

RBarryYoung (talk) 20:55, 1 March 2014 (UTC)

Missing steps in that proof?

The proof is basically that of Hopcroft and Ullman (1973). However, this short version does not clearly make use of the hypothesis that each Find leads to a path compression, which is crucial for the result to be correct. An extra explanation showing where and how that hypothesis is used seems needed. — Preceding unsigned comment added by Bsalvy (talk • contribs) 21:26, 15 November 2018 (UTC)

It is used (implicitly) in the argument to bound T_3. I'll try to augment that argument in the article. Preciser (talk) 02:06, 19 January 2019 (UTC)

Gaps in the proof

As I read the current proof, it reads as if the forest is unchanging. The original proof by Hopcroft and Ullman is careful (when defining the ranks, and when proving the analogous lemmas), to carefully account for how the trees change as a result of find and union operations. This issue seems to be swept under the rug in the current proof here, making it very hard to understand the details. Nealeyoung (talk) 23:18, 22 March 2019 (UTC)

References