# Analysis of Union Find with path compresson and rank

I have been given that $n$ make-sets and $m \ge k$ finds and $k$ unions can be performed in $O(n + m \log^*(k))$ time (I'm aware of the ackermann function but am not interested in proving that). Where $log^*(k)$ is $0$ if $k \le 1$ and $1 + log^*(log(k))$ otherwise.

The $n$ part is easy -- that's due to the number of make-sets. I'm having problems with the $m \log^*(k)$ part, which must then encompass union and find. Union is a constant cost + 2 finds.

I have been given the proof idea of spending $2^p$ credits when a node $x$ of rank $r \in \{p+1, ..., 2^p\}$ ("group p") stops being a root. $2^p$ ensures we're always in credit because it prepays for the potential $2^p$ existing children following a parent pointer to x (each kid can follow its parent pointer once before it's just added onto the root, where we pretend it's a constant cost)

The number of nodes in group p is $$\le \sum_{i=p+1}^{i=2^p} \frac{n}{2^{i}} \le \frac{n}{2^p}$$

And so in total, any group p gets $\le \frac{n}{2^p} \times 2^p = n$ credits.

There are $\le log^*(k)$ groups in total (because the greatest rank is $log(k)$).

Therefore a total of $\le n \log^*{k}$ credits are spent.

I'm under the impression that the accounting method is where the actual cost will be less than the total amount of credit spent (provided we are always in credit).

So this analysis gives $O(n + n \log^*(k) + m + k)$, which isn't what I wanted.

Edit to add question: What's wrong with the method above?

• But what is your question? Please take a look at the tour to get a better idea of how the site works. – David Richerby Apr 10 '17 at 19:20
• Sorry, my question is "what's wrong with my analysis because it's not giving the textbook result?" I'll make that more clear. – sam Apr 10 '17 at 19:26
• OK, but we're not a big fan of "What's wrong with my working?" questions -- see meta posts one and two. The problem is that such questions can be rather time-consuming to answer but they're unlikely to be interesting to anybody but the person who originally asked. – David Richerby Apr 10 '17 at 19:35
• Okay, I understand. Is there a better place to ask my question, or is there a way I can reword it to make it more interesting? edit: I had initially decided to include my working so that I could prove that I tried as hard as I could, but if it's making the question worse I can remove it – sam Apr 10 '17 at 21:32
• Thanks for looking for ways to improve your question! Are there concepts you're unsure about? Can you abstract out the concept you're having trouble with? A good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. Do you have a good understanding of amortized analysis and the accounting method? If not, it might be worth studying that material, then seeing if you have any specific question about that kind of analysis. This page might also be helpful. – D.W. Apr 10 '17 at 22:50