1
$\begingroup$

Let's define: $ a_i:a_j \Longleftrightarrow a_i < a_j;\ a_i=a_j;\ a_i > a_j $
So it is similiar to normal operation $<$, but $:$ give information when elements are equal.
I want show that lower bound for sort array of $n$ elements with this operation is $\Omega (n\log n)$.

I know proof for normal comparison. Nevertheless I can't solve it, I thought about it a long time, but without effect. Can you help me ?

(It isn't homework, nowadays I am on holiday :))

$\endgroup$
  • 1
    $\begingroup$ I can't tell what you mean by your notation after "Let's define". Do you mean that $:$ is an operation that takes two numbers and returns whether the first is smaller, they're equal, or the second is smaller? If so, you can do this by reduction: show a sorting algorithm that used $o(n\log n)$ of these comparisons would be impossible because it could also be programmed using $o(n\log n)$ ordinary comparisons. Then show that any comparison sort algorithm that uses ordinary comparisons can be rewritten to use the same number of these three-way comparisons. $\endgroup$ – David Richerby Aug 10 '15 at 19:22
  • $\begingroup$ You properly understand this definition. Ok, I will edit and try use your hint, $\endgroup$ – M.Swe Aug 10 '15 at 19:28
  • 1
    $\begingroup$ Looks good to me. However, rather than putting your answer in the question, I'd recommend turning it into a proper answer. It might feel a bit weird to post an answer to your own question but it's actively encouraged. On the other hand, putting the answer in the question and asking "Is this correct?" isn't really satisfactory, since the only possible answers are "yes" and "no", which aren't very interesting to anyone but you. $\endgroup$ – David Richerby Aug 10 '15 at 19:35
1
$\begingroup$

Let's suppose that it is possible to sort it with $:$ in time $o(nlogn$). So we use ordinary comparisons: $<$ and $>$. If both $a_i<a_j $ and $a_j > a_i$ is not truth then we conclude $a_i=a_j$. And now, we can sort in time: $o(2nlogn)=o(nlogn)$ - it is impossible.

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