Member Avatar for fashxfreak

Are there any O(n) algorithms to check if a 2d array is symmetric?

  • 4 Contributors
  • 3 Replies
  • 136 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by m4ster_r0shi

Dani AI

Generated

The term "symmetric" needs a quick disambiguation: most algorithmic discussions mean a matrix equal to its transpose (A[i][j] == A[j][i]). Other notions exist (horizontal/vertical mirror or 180-degree rotation). The snippet from checks center/rotation symmetry rather than transpose symmetry, and rectangular arrays cannot be transpose-symmetric without being square.

For an exact, deterministic test of transpose symmetry on a general square matrix, the practical implementation checks only one triangular half and exits on the first mismatch. That gives the minimal work in typical cases, but worst-case verification requires examining a large fraction of entries. If the matrix is sparse, complexity scales with the number of stored entries rather than the full dense size; verifying each nonzero (i,j) has a matching (j,i) in the sparse structure is the right approach there.

When full certainty is not required, two useful alternatives reduce work drastically in practice:

  • Randomized sampling (property testing): test a small number of random off-diagonal pairs. A few samples catch many realistic errors with high probability, but this is probabilistic and can miss small, targeted differences.
  • Signature/hash methods: compute compact row signatures and compare them to column signatures. Strong hashes make false positives unlikely, but collisions are possible unless cryptographic hashes are used, and worst-case inputs can defeat this.

Implementation tips not yet covered in the thread: iterate only over one triangle (i < j) to avoid duplicate checks; use cache-friendly loops (row-major order for row storage); for integer/POD data prefer block comparisons (memcmp) when applicable; for floating-point data compare with a well-chosen relative epsilon rather than exact equality. Overall choice depends on whether correctness must be absolute or a probabilistic/approximate check is acceptable, and on matrix density and memory constraints.

Recommended Answers

All 3 Replies

Member Avatar for mike_2000_17

No. The best algorithm is to check that all off-diagonal terms are equal (within a tolerance). And, there are (N^2 - N) / 2 checks to be done, which is of order O(n^2).

Edited by mike_2000_17 because: n/a
Member Avatar for NathanOliver

Wouldn't this be O(n)?

bool CheckSymmetric(int grid[maxrow][maxcol])
{
	int counter = 0;
	for (int i = 0, m = maxrow - 1; i < maxrow; i++, m--)
	{
		for (int j = 0, n = maxcol - 1; j < maxcol; j++, n--)
		{
			if (grid[i][j] != grid[m][n])
				return false;
		}
	}
	return true;
}
Edited by NathanOliver because: n/a
Member Avatar for m4ster_r0shi

It depends.

If n denotes the number of rows (or columns - it's the same, since it doesn't make sense to
check if a rectangular matrix is symmetric), then the above algorithm's complexity is O(n^2).

But if n denotes the number of elements, then, yes, the above algorithm's complexity is O(n).

Edited by m4ster_r0shi because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.