3
$\begingroup$

Is there any algorithm that works better than $\Theta(n^2)$ 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.

$\endgroup$
4
  • $\begingroup$ what algorithm do you already have for verification? $\endgroup$
    – Sim
    Apr 23, 2012 at 10:33
  • $\begingroup$ There is always the possibility of a big number of processors, then you can reduce your time complexity with a parallel algorithm. $\endgroup$
    – Gopi
    Apr 23, 2012 at 15:58
  • 3
    $\begingroup$ Maybe the n they refer to is the input size (n = NxN). So both can be valid, depending on how you define n. $\endgroup$
    – George
    Apr 23, 2012 at 16:27
  • $\begingroup$ Don't you normally also have to check whether all numbers are distinct? Or is this a different type of magic square? $\endgroup$
    – Mark
    Nov 3, 2016 at 11:31

1 Answer 1

4
$\begingroup$

If you have an $N \times N$ matrix, then it has $N^2$ entries, and as you need to check all entries at least once to see if the square is a magic square, any algorithm must have a running time of $\Omega(N^2)$.

For a square to be a magic square, all rows, columns and both diagonals must sum to the same number. There are $N$ rows, $N$ columns and 2 diagonals, each of which have $N$ entries, so you can check this property in $O((2N+2)N) = O(N^2)$ time.

Combining the above: verifying the magicness of a square is in $\Theta(N^2)$.

$\endgroup$
5
  • $\begingroup$ What if you have a sparse representation? $\endgroup$
    – Joe
    Apr 23, 2012 at 19:34
  • $\begingroup$ @Joe: that will strongly depend on the representation used. The entries of magic squares are usually distinct, so you can't just 'leave out all the 0 entries'. I'm not aware of any particular representation that is used often in this case. $\endgroup$ Apr 23, 2012 at 20:18
  • $\begingroup$ Distinct entries wasn't listed as an assumption in the problem statement. My point is that while you clearly have to spend time proportional to your input size, the input size isn't necessarily required to be $N^2$, unless we put additional constraints. (still upvoted, btw. Your answer is definitely useful) $\endgroup$
    – Joe
    Apr 23, 2012 at 20:25
  • 1
    $\begingroup$ @Joe With a sparse representation, you might get an $o(N^2)$ running time for some cases, but not in a case where your representation is complete. There have to be cases where the representation is complete (assuming the domain of the entries has at least two elements), because otherwise your representation would be a universal compression method. Hence the worst case complexity is indeed at least $\Omega(N^2)$. $\endgroup$ Apr 23, 2012 at 21:09
  • $\begingroup$ But if it is not a magic square then you may be able to prove that a lot quicker - just taking the sums of the first two rows, for example, will often prove that it is not a magic square. Of course worst case is still $O(n^2)$ even if it is not a magic square. $\endgroup$
    – gnasher729
    Jun 28, 2017 at 23:17

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.