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