Revision as of 12:18, 11 July 2023 edit AmirOnWiki (talk \| contribs) 401 edits Trying to make the statement of Tarjan's and Fredman-Saks results more precise ← Previous edit		Revision as of 12:21, 11 July 2023 edit undo AmirOnWiki (talk \| contribs) 401 edits add 'amortized' to infobox Next edit →
Line 8: \|space_avg = {{math\|O(''n'')}}<ref name="tarjan1975">{{cite journal\|last1=Tarjan\|first1=Robert Endre\|author1-link=Robert E. Tarjan\|year=1975\|title=Efficiency of a Good But Not Linear Set Union Algorithm\|journal=Journal of the ACM\|volume=22\|issue=2\|pages=215–225\|doi=10.1145/321879.321884\|hdl=1813/5942\|s2cid=11105749\|hdl-access=free }}</ref> \|space_worst ={{math\|O(''n'')}}<ref name="tarjan1975"/> \|search_avg={{math\|O(''α''(''n''))}}<ref name="tarjan1975"/> (amortized) \|search_worst={{math\|O(''α''(''n''))}}<ref name="tarjan1975"/> (amortized) \|insert_avg ={{math\|O(1)}}<ref name="tarjan1975"/> \|insert_worst ={{math\|O(1)}}<ref name="tarjan1975"/>

Disjoint-set data structure: Difference between revisions