Analyze the worst-case complexity of the CR algorithm below. Note that the secon
ID: 3886371 • Letter: A
Question
Analyze the worst-case complexity of the CR algorithm below. Note that the second inner for loop will change at least one element of every row to be -1. Input: M: n times n matrix of positive integers Input: W: n times n matrix of positive integers Input: n: dimension size for M and W Output: a mysterious array of length n Algorithm: CR sel = Array(n) repeat for every row r of M do if this row contains a positive integer then Let c be the column containing the smallest positive integer in row r Subtract M[r, c] from every integer in row r end for every column c of M do Count the number of zeros in column c if there is one zero then Let r be the row containing this 0 Set all other entries in row r and column c of M to be -1 sel[c] = r else if there is more than one zero then Consider the rows of column c in W that contain a 0 in column c of M Let r be the row containing the minimum of these values (break ties arbitrarily) Change all zeros in column c of M that are not in row r to - 1 end until no row of M contains a positive integer return selExplanation / Answer
Analysis:
The outer for loop runs for every row, Since there are total n rows and we visit each row atleast once So time taken by for loop is n.
The inner loop runs for every column iince there are total n columns and we visit each cols atleast once So time taken by for loop is n but inside the for loop we count zeros for each columns that counts for n time, i.e n2
If there are is one zero, for that column, we visit entire row, Suppose we do this for all columns it will take n2 time
else
we change all values in column c that are not in row r-1 which itself taken n time and for n columns n2 time
So Overall the Worst cas etime complexity is O(n2 )
Thanks, let me know if there is any concern.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.