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

Question

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.

Answer 1

Yes, you are correct!

You have identified a typo in that book, Algorithms, the fourth edition by Robert Sedgewick and Kevin Wayne. Please check the errata for the first printing (March 2011) of the fourth edition.

p. 226

Printed: in the worst case, it needs 2 N + 1 array accesses
Fixed: in the worst case, it needs 2 N - 1 array accesses
Reported by Victoria Solomon, 15-Sep-11.