Algorithm enigma find What  does the Algorithm  compute, input  size, basic operation


Algorithm enigma (A[0----n-1,0------n-1]
   for  i ← 0 to  n-2  do
      for  j ← i+1  to n-1   do
      if  A[ i, j]   ≠ A[j, i]
          return FALSE
      END  for
 return TRUE
END  Algorithm
  1. What  does the Algorithm  compute
  2. What  is  its input  size
  3. What  is its basic operation
  4. How many  times  is the basic operation executed
  5.  What is the efficiency  class of this algorithm

Answer :-

  1. What does the Algorithm compute?
    • The algorithm checks if a given square matrix A is symmetric. A square matrix is symmetric if it is equal to its transpose, meaning that A[i][j] should be equal to A[j][i] for all i and j.
  2. What is its input size?
    • The input size for this algorithm is n, which represents the size of the square matrix A. Specifically, the matrix is n x n.
  3. What is its basic operation?
    • The basic operation in this algorithm is the comparison of two matrix elements: A[i][j] and A[j[i].
  4. How many times is the basic operation executed?
    • The basic operation is executed in the nested loops. The outer loop runs from 0 to n-2, and the inner loop runs from i+1 to n-1. Therefore, the basic operation is executed (n-1) + (n-2) + … + 2 + 1 times, which is the sum of the first (n-1) natural numbers. This sum can be calculated as (n-1)*n/2.
  5. What is the efficiency class of this algorithm?
    • The time complexity of this algorithm can be expressed as O(n^2) since the basic operation is executed approximately (n-1)*n/2 times, and in big O notation, we drop constants and lower-order terms. So, the efficiency class of this algorithm is quadratic, denoted as O(n^2).

Leave a Reply

Your email address will not be published. Required fields are marked *