Hey everyone,

First off, I'm finally an expert! Thank you to everyone who has responded to my previous blog posts, your input helped me grow as a competitive programmer greatly!

Now, onto the actual question. What is the time complexity of using the "find" operation on an array-based union-find algorithm? First, let me put some pseudo-code of the union-find algorithm so that my ramblings will make more sense.

// We initialize the array such that each node is its own parent array = [0, 1, 2, 3, 4, 5... n]

// Find the "root" of a node function find(index): while (array[index] != index) index = array[index]

return index

// Join the "roots" of two nodes function union(a, b): array[find(a)] = array[find(b)]

Please someone correct me if my implementation is wrong or if there's any way I can improve my pseudo-code. Now, onto the actual question.

Let's imagine you have a straight, directed graph with randomized node order. For example: 3 --> 5 --> 1 --> 2 --> 4. I speculate that the time complexity of generating the union-find array is at worst n^2, and that once the array is generated, the time complexity of finding the root from any given node is at worst n. Let's go through the example I provided, assuming that we join nodes starting from the lowest node (1), then the second lowest (2), etc.