Content deleted Content added
→Making new sets: O(n) is linear time complexity |
m The interval for B bucket will be [tower(B-1),tower(B)-1] example for 2nd bucket it is [tower(1),tower(2)-1] = [2,3]. |
||
Line 217:
For <math>B \in \mathbb{N}</math>, let <math>\text{tower}(B) = \underbrace{2^{2^{\cdots^2}}}_{B \text{ times}}</math>. Then
bucket <math>B</math> will have vertices with ranks in the interval <math>[\text{tower}(B-1), \text{tower}(B)-1]</math>.
[[File:Proof_of_O(log*n)_Union_Find.jpg|center|frame|Proof of <math>O(\log^*n)</math> Union Find]]
| |||