# On the complexity analysis of quick-union in Algorithms by Sedgewick and Wayne

I am currently studying Algorithms, Fourth Edition by Sedgewick et al. On page 226, there is an analysis of the quick-union algorithm's find() method's worst case.

This is the algorithm:

  private int find(int p)
{ // Find component name.
while (p != id[p]) p = id[p];
return p;
}


Suppose we have originally an array from 0 to N-1. Now I count N comparisons in total (inside the while) plus N-1 accesses (last comparison is false) to rewrite the value of p. This would give me 2N - 1 accesses to the array. The textbook however says there are 2N+1 accesses. What am I doing wrong? Thanks for your time.

Computational complexity is being measured by the number of accesses to the array that we use to model which site belongs to which component. Suppose we want to connect the site labeled 3 with the site labeled 1. In order to do that we just make sure id[3]=1. The find() method exists to give us the component to which an element belongs. If we now connect 1 to 4, then we just make id[1] = 4. Now find(3) will be 4, because 3 points to 1 which in turn points to 4.

• The question would be hard to answer unless you tell us what $N$ is. Commented May 29, 2020 at 7:01