a What does this algorithm compute b Find the time efficienc

a) What does this algorithm compute?

b) Find the time efficiency class of the algorithm.

c) Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.

d) Is this algorithm based on the brute-force approach?

ALGORITHM Enigma(A[0..n -1, 0..n -1]) IInput: A matrix Ajo..n -1, of real numbers 1.0..n for 0 to n 2 do for j 1 to n -1 do if Ali, j] AU, il return false return true

Solution

a) This algorithm is checking whether the given Matrix is Transpose Matrix or not.

b) Since there are two loops nested running n number of times. So the time efficiency T(n) will be

T(n)= O(n²).

c)

No, you can not make it in less then O(n^2) and the reason behind this is that you need to at least touch each element in the matrix once (which is already (n*n). Therefore you can not do better.

Or you can do it in O(1) time but the space complexity will be increased in that way. Space complexity means additional memory space will be taken by the algorithm.

d.)

Yes this is brute-force aproach, since each element compared with each other once to prove the property of Transpose of the Matrix.