2]
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- What does the Algorithm compute
- What is its input size
- What is its basic operation
- How many times is the basic operation executed
- What is the efficiency class of this algorithm
Answer :-
- 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.
- 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.
- 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].
- 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.
- 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).