Hard
Union-find complexity under partial vs. full optimization
Consider three union-find implementations over n elements, subjected to a sequence of m union/find operations: (1) neither path compression nor union-by-rank (union always attaches an arbitrary root under the other; find walks parent pointers with no compression); (2) union-by-rank only, no path compression; (3) both union-by-rank and path compression together. Which statement correctly ranks their complexity?
8 of 46 in Data Structures & Algorithms