CSCI2100 · Theorem · Chapter 1 · Disjoint sets
Union by size bounds the depth
3 steps of prerequisites below it
With union by size every element of an n-element universe has depth at most ⌊log₂ n⌋, so each find takes O(log n) time, with or without path compression.
Taught in
Uses
- Parent forest · used in its proof, proof step 1.1
- Path compression · used in an argument or worked solution, passage 1.1
- Union by size · used in its definition, passage 1.1
Used by
No later knowledge point in these notes uses it.
Everything this builds on, earliest first · 4 steps
Each step comes after its own prerequisites, so reading in this order never needs something you have not met. It is a reading order for these notes, not a diagnosis of what you know.
- Partition · 1.1
- Parent forest · 1.1
- Path compression · 1.1
- Union by size · 1.1
Possible roots and a review route need your own answers on these points. None are recorded yet, so none are suggested.
Longest chain down to a starting point
Each step is used by the one above it, across courses where the notes link them. It ends at a point the notes define without another point.