Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following is an excerpt from a powerpoint on the role of the inverse Ackermann function in determining the complexity of path compression.

  • Dissection of a disjoint set forest $F$ with node set $X$

  • Partition of $X$ into “top part” $X_t$ and “bottom part” $X_b$ so that top part $X_t$ is “upwards closed”

  • i.e. $x∈X_t ⇒$ every ancestor of $x$ is in $X_t$ also

Using the definition of a "upwards closed" partition mentioned above, aren't there several distinct $X_t$ partitions that meet this criteria? Consider the following partitions that all appear to meet the aforementioned definition:

  • The first distinct partition is only the root.
  • The second distinct partition is the root and its children
  • The third distinct partition is the root, its children and its grandchildren
  • The remaining distinct partitions consist of the root and up to the $n^{th}$ generation of children

Do there exist multiple distinct "upwards closed" partitions in a disjoint set forest?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Yes, of course. This is just the definition of a "dissection"; there are several partitions that satisfy this definition. The upper part of a dissection need not contain all nodes at a given level; for example, it could consist of the root, just one of its children, and all of the descendants of that child.

The next few slides basically argue that you can analyze the effect of a series of path compressions on a forest $F$ by analyzing a corresponding sequence of path compressions in an arbitrary dissection of $F$. Then later, the slides show that by choosing a particular dissection (and arguing recursively), one obtains the inverse-Ackermann amortized time bound.

share|improve this answer
    
Thank you for the help. –  user26649 Jul 28 '12 at 4:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.