Find out order of two permutations

Question

Consider we have two different permutations of the numbers in this set: $\{1,2,...,n\}$

In each question we can ask about the order of two numbers in each of these permutations, for example if we ask for the order of $1,3$ in $(1,3,2)$ and $(3,2,1)$ we get the answer (lower,higher) respectively, which means that 1 comes before 3 in the first permutation and after 3 in the second.

Prove that the minimum order of questions that we have to ask and find out the order of both two permutations is $O(n\log(n))$

Answer 1

First of all, $O(n\log{n})+O(n\log{n})=O(n\log{n})$, in other words, if you first just ask all the questions to learn the first permutation, and then you just ask all the questions to learn the second permutation, you still get the complexity of $O(n\log{n})$.

Second, to learn a permutation, you (internally, in your head) perform any sort algorithm. For example, if the unknown permutation is $(3,5,1,6,4,2)$ and you want to use "merge sort", you would ask:

• About the order of the first half ($1$, $2$, $3$):

  • Order of $1$ and $2$ ("lower"): $1$ goes before $2$
  • Order of $1$ and $3$ ("higher"): $3$ goes before $1$, so we now know $1$, $2$, $3$ are ordered as $3,1,2$.

• About the order of the second half ($4$, $5$, $6$):

  • Order of $4$ and $5$ ("higher"): $5$ goes before $4$.
  • Order of $5$ and $6$ ("lower"): $6$ goes after $5$ so still need to check with respect to $4$
  • Order of $4$ and $6$ ("higher"): $6$ goes before $4$ so we now know $4$, $5$, $6$ are ordered as $5,6,4$.

• Merging:

  • Order of $3$ and $5$ ("lower"): $3$ is the smallest.
  • Order of $1$ and $5$ ("higher"): $5$ is the next smallest
  • Order of $1$ and $6$ ("lower"): $1$ comes next
  • Order of $2$ and $6$ ("higher"): $6$ comes next
  • Order of $2$ and $4$ ("higher"): $4$ comes next
  • Finally, $2$ is last.

It is well known that sorting algorithms have minimum complexity of $O(n\log{n})$, and merge sort above has that complexity. See e.g. https://en.wikipedia.org/wiki/Sorting_algorithm.