0
$\begingroup$

I am trying to prove that you can't sort binary heap with better complexity than O(nlogn). We proved at class that every sort based on comparison can't have better cocmplexity than O(nlogn) and i know nothing about the items in the heap (except its a heap) so you can't use radix sort or linear sort. Problem is i feel like its not enough to say this things. I don't know how i am supposed to prove it and i am searching for help.

$\endgroup$
1
  • 2
    $\begingroup$ If you want to prove that there are no "quick" algorithms for some problem $P$, and you know of some problem $Q$ that provably can't be solved "quickly", you can try to reduce $Q$ to $P$: To come up with a way of "quickly" transforming any instance of $Q$ to an instance of $P$. The reason is that then, if some algorithm exists that "quickly" solves all instances of your problem, it could also be used to quickly solve all instances of $Q$ -- a contradiction, implying that there is no such "quick" algorithm for your problem $P$. $\endgroup$ Commented May 6, 2021 at 11:48

1 Answer 1

1
$\begingroup$

A binary heap with $n$ elements can be built in time $O(n)$. If there was a (comparison based) sorting algorithm capable $A$ of sorting the elements in a heap in time $o(n \log n)$ then you could obtain a (comparison-based) sorting algorithm $A'$ that works for arbitrary sequences $S$ of $n$ elements. Algorithm $A'$ is as follows:

  • Construct a heap $H$ from $S$.
  • Execute $A$ with input $H$.

Such an algorithm requires time $O(n) + o(n \log n) \in o(n \log n)$ and hence it contradicts the $\Omega(n \log n)$ lower bound on comparison-based sorting algorithm. Therefore, algorithm $A$ cannot exist.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.