Question

Find the worst-case complexity of the algorithm below. Show your work.

UFSizeCalc

Input:  uf: Union-Find array of size n

Input: n: size of uf

Output: size array for uf; that is, an array s such that s[r] equals the number of elements in the Union-Find tree rooted at r, for every root r (s may have any value for indexes that are not roots of uf)

Pseudocode:

For i = 1 to n

uf.Find(i)

size = Array(n)

Initialize size to be 0

For i = 1 to n

    size[uf[i]] = size[uf[i]] + 1

Return size

Show your work

Answer 1

Please find the algorithm below with inline description of the time complexity

Pseudocode:

For i = 1 to n ------> this loop runs n times for i = 1, 2, 3, 4, ....., n

uf.Find(i) ---> Find() operation takes O(log n)

size = Array(n) ---> this statement takes O(1)

Initialize size to be 0 ----> this statement takes O(1)

For i = 1 to n ------> this loop runs n times for i = 1, 2, 3, 4, ....., n

    size[uf[i]] = size[uf[i]] + 1 ---> this statement takes O(1)

Return size ---> this statement takes O(1)

Hence, the total time complexity is:

n * log (n) + 1 + 1 + n + 1

= O(n log n)