Question

Find the worst-case complexity of the algorithm below. Show your work. UFSizeCalc Input:  uf: Union-Find array of...

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

Homework Answers

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)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Analyze the worst-case complexity of the algorithm below when using an optimized adjacency list to store...
Analyze the worst-case complexity of the algorithm below when using an optimized adjacency list to store G. ComponentCount: Input: G = (V, E): an undirected graph with n vertices and m edges Input: n, m: the order and size of G, respectively Output: the number of connected components in G Pseudocode: comp = n uf = UnionFind(n) For v in V:     For u in N(v):         If (uf.Find(v) != uf.Find(u))             uf.Union(u, v)             comp = comp - 1...
Analyze the worst-case complexity of the algorithm below when using an optimized adjacency list to store...
Analyze the worst-case complexity of the algorithm below when using an optimized adjacency list to store G. ComponentCount: Input: G = (V, E): an undirected graph with n vertices and m edges Input: n, m: the order and size of G, respectively Output: the number of connected components in G Pseudocode: comp = n uf = UnionFind(n) For v in V:     For u in N(v):         If (uf.Find(v) != uf.Find(u))             uf.Union(u, v)             comp = comp - 1...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
Using the following code perform ALL of the tasks below in C++: ------------------------------------------------------------------------------------------------------------------------------------------- Implementation: Overload input...
Using the following code perform ALL of the tasks below in C++: ------------------------------------------------------------------------------------------------------------------------------------------- Implementation: Overload input operator>> a bigint in the following manner: Read in any number of digits [0-9] until a semi colon ";" is encountered. The number may span over multiple lines. You can assume the input is valid. Overload the operator+ so that it adds two bigint together. Overload the subscript operator[]. It should return the i-th digit, where i is the 10^i position. So the first...
Consider the C program (twoupdate) to demonstrate race condition. In this assignment, we will implement Peterson's...
Consider the C program (twoupdate) to demonstrate race condition. In this assignment, we will implement Peterson's algorithm to ensure mutual exclusion in the respective critical sections of the two processes, and thereby eliminate the race condition. In order to implement Peterson's Algorithm, the two processes should share a boolean array calledflagwith two components and an integer variable called turn, all initialized suitably. We will create and access these shared variables using UNIX system calls relating to shared memory – shmget,...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT