1
$\begingroup$

Given an array of integers $(a_1,\ldots,a_N)$, what is an efficient method to compute the matrix $A\in\mathbb{Z}_2^{N\times N}$ whose $(i,j)$ entry is $1$ if $a_i < a_j$, and $0$ otherwise?

By efficient I mean something better than comparing all elements pairwise, which requires $O(N^2)$ comparisons.


CONTEXT

I am aware that the brevity of the question may make it unclear. I will try to clarify with an example. To sort an array of length $N$ one may use $O(N^2)$ comparisons, but it's quite a shocking fact that we can do it with much less: $O(N\log N)$. Intuitively, only $O(N\log N)$ comparisons are necessary to completely determine all the relations among the array.

Now, what I am asking here is whether a similar thing holds for the comparison matrix. Can we compute, say $O(N\log N)$ comparisons, and from these infer all the entries from the comparison matrix? Again, just like in the sorting case, we can compute all these $N^2$ entries separately using one comparison for each, but can we do better?

$\endgroup$
  • $\begingroup$ I guess you don't want us to reorder the array, and then create the matrix for that reordered array? $\endgroup$ – Sudix Jul 30 at 23:40
  • $\begingroup$ @Sudix Thanks for the comment. Isn't the matrix for the reordered array trivial? $\endgroup$ – Daniel Jul 30 at 23:41
  • $\begingroup$ It is, but that is the first step I would do if I'd try to optimize. If you want the matrix to be fixed, that would force me to throw permutation matrices on it afterwards, which most likely would put us in $O(N^2)$ again anyway. $\endgroup$ – Sudix Jul 30 at 23:46
  • 2
    $\begingroup$ @Daniel What do mean by "compute"? For an already ordered/reordered array, the matrix will be upper triangle with zero diagonal and $1$'s in the triangular part. Such a matrix has $\frac{N(N - 1)}{2}$ i.e. $O(N^2)$ non-zero entries. So computing only the non-zero entries is still an $O(N^2)$ operation even in this best case scenario of an ordered array. $\endgroup$ – 0XLR Jul 30 at 23:49
  • $\begingroup$ @ZeroXLR I apologize for the lack of clarity. I tried to make it clearer, please let me know if it makes sense. $\endgroup$ – Daniel Jul 31 at 0:01
2
$\begingroup$

It depends on how you seek to represent $A$. If you represent $A$ by storing only the index pairs $(i, j)$ where $A_{ij} = 1 \neq 0$, you cannot do better than $O(N^2)$.

For any such pair $(i, j)$, either $a_i < a_j$ or $a_i \geq a_j$ by trichotomy. So unless $i = j$, either you have to store $(i, j)$ or you have to store $(j, i)$. Thus, you are guaranteed to do $$ \Big(\sum_{k = 1}^N k \Big) - N = \frac{N(N - 1)}{2} \sim O(N^2) $$ storing operations just to instantiate $A$.

However, if you seek to represent $A$ as an algorithm that answers the following question:

For a certain index $(i, j)$ is $A_{ij} = 1$ or is $A_{ij} = 0$?

Then it is trivial: if $a_i < a_j$, you output $1$ and $0$ otherwise.

$\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.