✦ LIBER ✦
Lower Bounds for the Union–Find and the Split–Find Problem on Pointer Machines
✍ Scribed by Han La Poutré
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 490 KB
- Volume
- 52
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
A well-known result of Tarjan states that for all n and m n there exists a sequence of n&1 Union and m Find operations that needs at least 0(m . :(m, n)) execution steps on a pointer machine that satisfies the separation condition. Later the bound was extended to 0(n+m. :(m, n)) for all m and n. In this paper we prove that this bound holds on a general pointer machine without the separation condition and we prove that the same bound holds for the Split Find problem as well.