-1
$\begingroup$

"If every element comparison (testing whether $a_i \le a_j$ ) provides at most one bit of information, argue that you need at least on the order of $\ln(n!)$ many tests/comparisons to sort the list."

This is a question on my homework at the moment. I don't understand how I'm supposed to go about arguing this as I don't quite understand why it is true. Any pointers in the right direction? Thanks.

$\endgroup$
  • 2
    $\begingroup$ There should be explicit pointers in your course material such as textbook or lecture note. Can you summarize what you had learned just before this homework? $\endgroup$ – Apass.Jack Nov 24 '18 at 1:02
  • $\begingroup$ This question is in reference to what was taught a few lectures back and so I can't recall it as well as I should but we proved the worst case Big Oh time-complexity of merge sort and insertion sort. Our professor talked about the minimal amount of work required to sort a list but I'm a bit lost on that part although I feel as if the answer is related to that. $\endgroup$ – toshko3331 Nov 24 '18 at 1:11
  • $\begingroup$ @toshko3331 Search for lower bounds on sorting, you should get your answer. $\endgroup$ – Gokul Nov 24 '18 at 1:57
1
$\begingroup$

You should model the comparison based sorting problem with decision tree where each node represents a comparison. You should see there are $n!$ leaves of such tree each contributes to a possibility of sorted array. If $h$ is the height of such tree, then $2^{h} \geq {n!}$ follows.

$\endgroup$
0
$\begingroup$

If an array contains n different items, these can be arranged in n! permutations. To sort an array, you must know which of the n! possible permuatations yu started with.

So you start with n! possible permutations. With one decision, in the best possible case n! / 2 of these permutations will give an answer "yes", and the other n! / 2 of these permutations will give an answer of "no". So with one single decision, you can reduce the possibilities from n! to n! / 2.

With k decisions, you may be able to reduce the possibilities to $n! / 2^k$ possibilities. You need to reduce the possibilities to only one, and for that you need to make at least $log_2 (n!)$ decisions.

With fewer than $log_2 (n!)$ decisions, there must be at least two permutations where all those decisions would give the same outcome, and since you don't know which of these two permutations you started with, you can't sort both permutations correctly.

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