Magic square check for N×N matrix with minimum complexity

algorithmscomplexityperformance

Is there any algorithm that works better than O(n²) to verify whether a square matrix is a magic one (e.g. such as sum of all the rows, cols and diagonally are equal to each other)?

I did see someone mention a O(n) time on a website a few days ago but could not figure out how.

Best Answer

It all depends on what n is. If you say that n is the number of ellements per row you cant check if the matrix is magic with less than O(n²). If you say n is the total number of ellements in the matrix you could easily create an algorithm that has the time complexity of O(n).

Here is some psevdo code with time complexity analys

columvalue = rows[0];                    O(1)
diagonalvalue1 = rows[0][0]              O(1)
diagonalvalue2 = rows[0][-1]             O(1)
magicNumber = sum(rows[0]);              O(c)
diagonal count = 1

for r in rows:                           O(r)*(
  diagonalvalue1 += r[0+diagonalcount]         O(1)
  diagonalvalue2 += r[-1-diagonalcount]        O(1)
  diagonalcount  += 1                          0(1)
  rowsum = 0                                   O(1)
  i = 0                                        O(1)
  for n in r:                                  0(c)*(
    rowsum += n                                     O(1)
    columvalue[i] += n                              O(1)
    i += 1                                          0(1)
                                                    )
  if rowsum != magicvalue:                     O(1)
    return False                               O(1)
                                               )

for c in columvalue:                     O(c)*(
  if c != magicvalue:                          O(1)
    return False                               O(1)
                                               )

return diagonalvalue1 == magicvalue and 
       diagonalvalue2 == magicvalue       O(1)

this will give us the time complexity of O(c) + O(r*c) there c = number of colons and r = number of rows. Since O(r*c) >= O(c) we can say that the time complexity is O(r*c) which are the number of ellements in the matrix that are n and this gives us the complexity of O(n)

Related Topic