Analyze the worst-case complexity of the CR algorithm below. Note that the secon

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 sel

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

Navigate

• Browse (All)
• Browse A
• Subjects

---