OBI Practice Questions - Olimpíada Brasileira De Informática Exam

Access More Questions

When implementing a Disjoint Set Union (DSU / Union-Find) data structure with both path compression and union by rank (or size), what is the amortized time complexity per find/union operation?

O(1) strictly worst-case time per individual operation O(log N) amortized time per operation O(sqrt(N)) amortized time per operation O(alpha(N)) amortized time per operation, where alpha is the extremely slow-growing inverse Ackermann function

Correct Answer:

O(alpha(N)) amortized time per operation, where alpha is the extremely slow-growing inverse Ackermann function

Access more questions from this quiz

Continue to OBI Practice Questions - Olimpíada Brasileira de Informática Exam for more practice questions and the full quiz experience.

Access More Questions