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 Apr 23 '12 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/… – Bill the Lizard Apr 23 '12 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 Apr 23 '12 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.) – Bill the Lizard Apr 23 '12 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 Apr 23 '12 at 13:45

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)

|improve this answer|||||
  • 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. – Kris Harper Apr 23 '12 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 Apr 23 '12 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 Apr 23 '12 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. – Donal Fellows Apr 23 '12 at 13:06
  • @DonalFellows: en.wikipedia.org/wiki/Big_O_notation – vartec Apr 23 '12 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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