Question

. We have the following algorithm.
Algorithm Novel(X[0..m-1, 0..m-1])
//Input: A matrix X[0..m-1, 0..m-1] of real numbers
for i←0 to m-2 do
for j←i+1 to m-1 do
   if X[i,j] ≠X[j, i]
       return false
return true

a.   What does this algorithm compute?

b. What is its basic operation?

c. How many times is the basic operation executed?

d. What is the efficiency class of this algorithm?

Answer 1

• Below is the detailed explanation of the above mentioned problem.
• Algorithm:

Algorithm Novel(X[0..m-1, 0..m-1])
for i←0 to m-2 do
for j←i+1 to m-1 do
if X[i,j] ≠X[j, i]
return false
return true

The above algorithm is trying to check if the given matrix X(of dimension mm) is symmetrix or not i.e, it is checking if all the element at X[i,j] are equal to X[j,i], if not then it is returning false otherwise after full checking it returns true.

A symmetric matrix is a matrix which is equal to it's transpose, so this matrix is symmetrix about left diagonal and on it's diagonal the element can be anything as for left diagonal in X[i,j] i=j so for diagonal X[i,j]=X[j,i] is true always irrrespective of the value.

• Answers:

a. So this algorithm is checking if the give matrix is symmetrix or not.

b.it's basic operation is to check if element at X[i,j] is equal to X[j,i] i.e, the sole condition for being a symmetrix matrix for all i,j in [0,m-1].

c.So the basic operation is executed (m*(m-1))/2 times (in worst case i.e, if the matrix is symmetric and it can be less if the matrix is asymmetric as we will reach the condition X[i,j] ≠X[j, i] and return from the function) as we can see that the outer for loop runs from u=0 to m-2 i.e, m-1 times and the inner loop runs from i+1 to m-1 i.e, m-i-1 times. So for each outer loop we get inner loop iterations as m-1(when i=0), m-2(when i=1).....................and at last 1(when i=m-2). So in total the sum of this series is 1+2+3+.................m-2+m-1= (m*(m-1))/2. So resultingly the number of times this operation is performed is (m*(m-1))/2.

d. the efficiency class of this algorithm is (m²) i.e, order of m² , as we can see that the number of times operation is performed is in total (m*(m-1))/2(in worst case if the matrix is symmetric) and 1(in best case if the matrix is asymmetric) so in average case in theta notation we can say that it is (m²)(also by the polynomial theorem) that it belong to this class.

Example of a symmetric matrix(33) ( X[i,j]=X[j,i] for all i,j in [0,m-1])

-1	2	3
2	0	4
3	4	5

Example of a asymmetric matrix(33) ( X[i,j]!=X[j,i] for all i,j in [0,m-1] i.e, in particular X[0,1]!=X[1,0] )

-1	2	3
3	0	4
3	4	5

So if you still have any doubt regarding this solution please feel free to ask it in the comment section below and if it is helpful then please upvote this solution, THANK YOU.