In practice, the amortized O(α(n)) data structure is good for every case. But if I want to be pedantic and require each operation to be under a certain time complexity, what's the currently known best complexity, and is it optimal?

The normal disjoint set implementation with recorded rank (height before optimization) could make it into O(log n). One could also get O(log n) using trees or heaps. But could it be better?

One possible use case is, if I found an algorithm mostly in O(log log n) but also has a disjoint set operation, it seems awkward to say it's amortized O(log log n) but at most O(log n) for each operation. Much better if it's just O(log log n) without "amortized".

  • $\begingroup$ Note that if an algorithm that uses disjoint set data algorithms internally happens to run it to completion, the "amortised" qualifier disappears. E.g., this is the case for Kruskal's MST algorithm. $\endgroup$ – j_random_hacker Nov 15 '20 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.