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

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).

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;
}

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).

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.