I have been trying to learn more about amortized analysis. Recently I came across the Disjoint Sets or Union-Find structures. I am using union by rank and path comparison. The potential of such data structures is sum of $\phi(x)$ for all nodes where

$$\phi(x) = \begin{cases} 0, & \text{if }\mathrm{rank}(x)=0 \\ \alpha(n)*\mathrm{rank}(x), & \text{if $x$ is the root} \\ (\alpha(n) - \mathrm{level}(x))\mathrm{rank}(x) - \mathrm{index}(x), & \text{otherwise.} \end{cases} $$

I could somehow successfully analyze the above potential function (trust me, it was really really hard for a beginner like me, but I somehow managed to do it). But I am getting stuck in the middle of my analysis when I change the definition of $\phi(x) $ to a simple $\mathrm{height}(x)$. It would be great if someone could help me learn more about this potential function and guide me how I could analyze the data structure when I change my potential function..

P.S : I tried reading documents online about the union-find(disjoint-sets) data structure. But as i read more about the data structure, my analysis is becoming more and more confusing. So if you could point me in the right direction, it would be great. Also, this is my first post here, so if I am in the wrong group and I need to ask the question else where, please let me know the right group where I can post this question.

  • 1
    $\begingroup$ I'm not sure how you expect us to help you fix an analysis that you haven't even shown us. Do you have a more specific question that you can ask with enough context to make it answerable? $\endgroup$ Oct 13 '16 at 19:10
  • $\begingroup$ I am really sorry about the bad wordings in my question. So i am trying to find the amortized analysis of the "find" operation of union-find data structure(using union by rank and path compression ) .My potential function is just the height of every node in the sets. Any explanation/guidance/help regarding how i could go about doing this would be helpful. $\endgroup$ Oct 13 '16 at 19:58
  • $\begingroup$ Welcome to CS.SE! However, I'm afraid the question seems a bit too unfocused/open-ended to be a good fit here. We prefer specific, answerable questions, where it's clear how to evaluate what would count as a correct answer. Here you seem to be asking for guidance about something (I'm not sure what, exactly), which makes it hard to know how to answer and hard to evaluate any proposed answers. $\endgroup$
    – D.W.
    Oct 14 '16 at 5:17

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.