3
$\begingroup$

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".

Improve this question
$\endgroup$
1
  • $\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
    Commented Nov 15, 2020 at 12:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.