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.

  • +1. Why was this rated down? Question is short, because no further explanation is required. Topic is suitable because, well, he's not going to find the answer on stackoverflow.com.
    – Neil
    Commented Apr 23, 2012 at 10:21
  • 1
    @Neil Why wouldn't he find an answer on Stack Overflow? Did you try searching? There are over 4600 results. stackoverflow.com/… Commented Apr 23, 2012 at 12:04
  • @BilltheLizard, this is not a question suitable for stack overflow. If it were there, it would quickly be moved here or to cstheory.stackexchange.com.
    – Neil
    Commented Apr 23, 2012 at 13:25
  • 1
    @Neil I'm a moderator on Stack Overflow. I know what's suitable there. There are any number of code samples on SO that answer this question. (Not that there's anything wrong with asking it here, I'm just pointing out that an answer can already be found on SO.) Commented Apr 23, 2012 at 13:32
  • It has been my experience that such questions are moved, @BilltheLizard. Code samples are a different matter I think, but this is borderline theoretical. Perhaps you have different experiences than my own then.
    – Neil
    Commented Apr 23, 2012 at 13:45

1 Answer 1


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)

  • The title says an NxN matrix, so I would assume n refers to the side length. Just curious, can you prove that you can't do better than O(n^2)? It doesn't seem obvious to me. Commented Apr 23, 2012 at 10:56
  • There is misconception here. n in big-O notation means data size; with N-by-N matrix, data size is N*N, not N.
    – vartec
    Commented Apr 23, 2012 at 11:00
  • 1
    Well by just using common sense it can be proved that to determine if the matrix is magic you have to look at all of it's ellement and therefore O(n).(All ellements have a possibility to change the outcome).
    – nist
    Commented Apr 23, 2012 at 12:55
  • 1
    @vartec Actually, the n is just some parameter and it ought to be documented exactly what it means. It's just that in some domains (e.g., searching, sorting) it is extremely well known what that parameter is. Commented Apr 23, 2012 at 13:06
  • @DonalFellows: en.wikipedia.org/wiki/Big_O_notation
    – vartec
    Commented Apr 23, 2012 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.