1
$\begingroup$

My idea is to use a proof by induction on $n$.

For $n = 1,2,3$, $1$ run is needed so we are done.

Assume the statement is true for sets of $n$ or less integers, $n > 3$. Let $S$ be a set of $n+1$ integers, and $p \in S$. By the induction hypothesis, it takes at least $k(n) = \lceil \operatorname{log}_6(n!) \rceil$ runs of the machine to sort $S \setminus \{p\}$.

At this point we’d have a sorted list $S \setminus \{p\}$ and want to know where $p$ should be inserted into this list. Let $k’$ be the number of runs required to do this task. A ternary search on the sorted list $S \setminus \{p\}$ could result in $k’ = \operatorname{log}_3(n)$ runs in the worst-case scenario (say, if $p$ is in the middle of the sorted list $S \setminus \{p\}$). Now we’d have:

\begin{align} k(n+1) &= k’ + k(n) \\ &= \operatorname{log}_3(n) + \lceil \operatorname{log}_6(n!) \rceil \\ &\geq \operatorname{log}_6(n+1) + \lceil \operatorname{log}_6(n!) \rceil \\ &\geq \operatorname{log}_6(n+1) + \operatorname{log}_6(n!) \\ &= \operatorname{log}_6((n+1)!), \end{align}

where the first inequality is true since $\operatorname{log}_3(n) \geq \operatorname{log}_6(n+1)$ holds for $n \geq 2$. So $k(n+1) \geq \lceil \operatorname{log}_6((n+1)!) \rceil$.

What I’m not sure of is whether I’m assuming too much what the algorithm would do in obtaining $k’$, or if it’s clear ternary search is the fastest way to do this task. Please give some comment.

$\endgroup$
1
$\begingroup$

There are $n!$ different possible ways to order the $n$ elements. After the first comparison, and subsequent ordering of the three compared elements, there are at still at least $\frac{n!}{6}$ possible orders the elements could have. After the second comparison, and subsequent rearrangement, there are at least $\frac{n!}{6^2}$ possible orders left.

At the very least, we need to keep going until that number reaches $1$. This will take $\lceil\log_6(n!)\rceil$ comparisons.

$\endgroup$
1
$\begingroup$

This is an exercise in decision trees. Each run has $3!=6$ possible results, but we need to distinguish between $n!$ results (corresponding to all permutations of $n$ distinct integers). The least depth of the decision tree that will allow for accommodating $n$ leaves is $\lceil\log_6n!\rceil$.

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