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)

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 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 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 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 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

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 5 minutes ago

asked 23 minutes ago

asked 59 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago