Suppose we have a set $S$ with $n$ elements, and let $\{X_1,\ldots,X_r\}$ and $\{Y_1,\ldots,Y_s\}$ be two partitions (clusterings) of $S$. I would like to know what is the time complexity for the algorithm that computes the Rand Index between these two partitions as a function of $n,r$ and $s$.
I am working on a special case where the partitions are always of a particular form, and for this case I proved an alternative formula that allows me to compute the Rand Index in $\mathbf{O}(rs)$. Thus, I would like to compare the complexity to the general case. Thank you!
The standard approach takes O(n) to tabulate the data.
Then O(rs) to process each cell in the table once.
So the worst case probably is O(n²) with most implementations, assuming that each object is it's own cluster in both the ground truth and the clustering (in which in the most extreme case using the Rand index is pointless, and you will get a division by zero). A more useful number is O(N+rs) or just O(N) assuming that there are relatively few clusters and many points. A sparse matrix data structure can be used to bound the complexity to O(N).