Notice
Recent Posts
«   2021/12   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
Tags more
관리 메뉴

## Complexity of union-find with path-compression, without rank 본문

Problem Solving/분류없음

### Complexity of union-find with path-compression, without rank

gumgood 2020. 2. 11. 11:27

### Q. Complexity of union-find with path-compression, without rank

Wikipeda says union by rank without path compression gives an amortized time complexity of $O(\log n)$, and that both union by rank and path compression gives ans amortized time complexity of $O(\alpha(n))$ (where $\alpha$ is the inverse of Ackerman funcion). However, it does not mention the running time of path compression without union rank, which is what I usually implement myself.

What's the amortized time complexity of union-find the path-compression optimization, but without the union by rank optimization?

### A.

Seidel and Sharir proved in 2005 [1] that using path compression with arbitrary linking rounghly on $m$ operations has a complexity of roughly $O((m+n)\log(n))$.

~ (작성 중)

#### 'Problem Solving > 분류없음' 카테고리의 다른 글

 Efficient program to print all prime factors of a given number  (0) 2020.02.11 2020.02.11 2020.01.16 2019.08.30 2019.05.08 2019.04.23