I finished a program to do connected component analysis using union - find algorithm. Is it true that the complexity of the code is \$O(N logN)\$, where \$N\$ is the total number of pixels (512x512 by example, not 512). Is there any way to improve the performance?import cv2import numpy as npimport randomclass QuickUnionUF:    def __init__(self, N):        self.id = range(N)        self.sz = [0] * N    @classmethod    def fromimage(self, im):        self.id = im        self.sz = [0] * len(im)    def root(self, i):        while (i != self.id[i]):            i = self.id[i]        return i    def getresult(self):        result = [self.root(i) for i in self.id]        return result    def connected(self, p, q):        return self.root(p) == self.root(q)    def union(self, p, q):        i = self.root(p)        j = self.root(q)        if (i == j):            return        if (self.sz[i] < self.sz[j]):            self.id[i] = j            self.sz[j] += self.sz[i]        else:            self.id[j] = i            self.sz[j] += self.sz[i]        def bwlabel(im):    M, N = im.shape[:2]    qf = QuickUnionUF(M * N)    for i in range(M - 1):        for j in range(N - 1):            if (im[i][j] == im[i][j+1]):                qf.union(i * N + j, i * N + j + 1)            if (im[i + 1][j] == im[i][j]):                qf.union(i * N + j, (i + 1) * N + j)    mask = np.reshape(np.array(qf.getresult()), (M, N))    values = np.unique(mask).tolist()    random.seed()    colors = [(random.randint(0,255), random.randint(0,255), random.randint(0,255)) for k in range(len(values))]    out = np.zeros((M, N, 3))    for i in range(M):        for j in range(N):            label = values.index(mask[i][j])            out[i,j] = colors[label]    return outim = cv2.imread(bw.jpg,cv2.IMREAD_GRAYSCALE)out = bwlabel(im > 100)cv2.imwrite(result.png, out)
Connected component analysis
python;performance
Is it true that the complexity of the code is O(NlogN), where N is the total number of pixels (512x512 by example, not 512).You main loop in bwlabelis:for i in range(M - 1):    for j in range(N - 1):        if (im[i][j] == im[i][j+1]):            qf.union(i * N + j, i * N + j + 1)        if (im[i + 1][j] == im[i][j]):            qf.union(i * N + j, (i + 1) * N + j)So you are calling qf.union \$O(N*M) = O(n)\$ times. There you call self.root twice:def root(self, i):    while (i != self.id[i]):        i = self.id[i]    return iWhat's the worst case running time of this? At most \$O(n)\$, since self.id has \$n\$ values and there are no cycles. However, since you are comparing ranks in union:    if (self.sz[i] < self.sz[j]):        self.id[i] = j        self.sz[j] += self.sz[i]    else:        self.id[j] = i        self.sz[j] += self.sz[i]        You will have \$O(log\ n)\$ paths to root, so the total running time is \$O(n\ log\ n)\$.Is there any way to improve the performance?Yes, path compression. You descended down two paths from p and q to i and j and it took \$O(log\ n)\$. At each step you can point a node to its root, instead of just the next element. You can do this recursively like so:def root(self, i):    if i == self.id[i]:        return i    self.id[i] = self.root(self.id[i])    return self.id[i]Recursion adds its own cost, though, so whether it's faster in practice would require testing. An alternative would be to add a second iterative compression function:def compress(self, i, r):    while i != r:        i, self.id[i] = self.id[i], rNow you are walking the path twice, which again may or may not be faster than recursion. You should only need to call this for one of the paths, though.