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?
Best Answer
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:
Then it is trivial: if $a_i < a_j$, you output $1$ and $0$ otherwise.