Suppose we have a sorting algorithm that in addition to regular comparisons, is

Question

Suppose we have a sorting algorithm that in addition to regular comparisons, is also allowed super-comparisons: a super-comparison takes in *three* elements and outputs those elements in order from smallest to largest. So, unlike a regular comparison that only has two possible answers, a super-comparison has 3! possible answers. Which of the following is a correct lower bound on the number of super-comparisons needed to sort an array of size n? (and give a brief explanation why) PLEASE GIVE AN EXPLANATION!

Explanation / Answer

O(n log6 n)

Let max no. of comparisons be f(n).

So number of unique cases it can distinguish is (3!)f(n)

Now total no. of cases: n!

so (3!)f(n) >= n!

so f(n) > =log6 (n!)

By stirlings approximation we get O(n log6 n).

Note normally we have O(n log2 n) for normal comparisons.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---