Minimum size of a subset to know a complete total order Lets say we have a set $A$. Suppose that $A$ is ordered by $<$, $A$ is completely ordered. 
$<$ can be defined as $<:=\{(a,b) \in A\times A : a<b \}$


*

*Given that $<$ is transitive, it is not necesary to know all the values of $<$, so what is the minimum amount of pairs in $<$ needed to know all the values of $<$. For example:
Let $A = \{a,b,c,d,e\}$. Suppose we know $a<b$, $c<d$, $d<e$, $ e<a$. From that, we can conclude that $c<d<e<a<b$, so we know all the values of $<$ .

*Is there an algorithm to find that/those minimum sets? 

 A: We need at least $n-1$ entries of $\lt$ to uniquely reconstruct the total order. Construct an undirected graph $G$ with vertex set $A$ by adding an edge $xy$ if and only if we know the relative ordering between $x$ and $y$. It is easy to see if the total order can be uniquely reconstructed from the entries, then $G$ must be connected; hence $G$ should have at least $n-1$ edges. 
In fact, $n-1$ entries suffice as well. For example, if we know that $a_1 < a_2 < \cdots < a_{n-1} < a_n$, then the total order is completely specified. 
A: The question is equivalent to "how many pairwise comparisons are needed to sort a list of $n$ elements?"  Clearly the answer must be at least $\log_{2}(n!)=n\log_{2}n + O(n)$ in the worst case, since there are $n!$ possibilities to distinguish and each comparison has only $2$ possible outcomes... this gives a lower bound.   On the other hand, there are examples of sorting algorithms that operate using $O(n\log n)$ comparisons (e.g., merge sort), giving an upper bound.  Therefore the answer is $\Theta(n\log_2{n})$.
I am assuming that you are allowed to choose which elements to compare based on the results of previous comparisons.  If you are not, then the answer is simply $\frac{1}{2}n(n-1)$: all pairwise comparisons need to be made.  For every pair $(a,b)$, there are orderings where $a$ and $b$ are adjacent and cannot be placed relative to each other without being directly compared.
