📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    Question

    Which data structure gives amortized O(α(n)) time for

    union and find operations, where α is inverse Ackermann?
    A Binary search tree Correct Answer Incorrect Answer
    B Disjoint-set (union-find) with union by rank and path compression Correct Answer Incorrect Answer
    C Hash table Correct Answer Incorrect Answer
    D Fibonacci heap Correct Answer Incorrect Answer
    E Van Emde Boas tree Correct Answer Incorrect Answer

    Solution

    Union-find with these heuristics yields nearly constant amortized time bounded by inverse Ackermann function.

    Practice Next
    More Algorithms Questions
    ask-question