1
$\begingroup$

So each matrix has $N^{2}$ elements, and so just by comparing each element we would be doing $O(N^{2})$ operations. Is there any other way to compare these two matrices such that the number of operations is less than $O(N^{2})$ or is the matrix comparison lower bound also $\Omega(N^2)$?

$\endgroup$
1
  • 2
    $\begingroup$ What kind of comparison are you looking at? $\endgroup$ – Raphael Feb 22 '16 at 13:43
4
$\begingroup$

A very simple adversary argument shows that when comparing two vectors of length $M$ (in your case, $M = N^2$), you must query (in the worst case) all positions of both vectors to know whether they are equal. That takes time $\Omega(M)$.

$\endgroup$
0
$\begingroup$

No, not normally, unless you constrain the type of the matrix further.

Theoretically, it is possible if you bound the input space and the type of the matrix. For example, suppose that we know that the matrices are both scalar matrices, such that they are identity matrices times two different scalar. In that case, it is necessary to only compare two elements; a diagonal element with a diagonal element from the other matrix. In this case, the algorithmic complexity would be $O(1)$. This is kind of a cop-out, however, as we are now computing on a specific subset of matrices.

This can be useful, however, if you do, in fact, know more specific traits about the data you are computing on.

$\endgroup$

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.