5
$\begingroup$

I've been given the following problem:

Given a data structure $M$ that is based on comparisons and supports the following methods on a group of numbers $S$:

  • $\text{Insert}(x)$ – add $x$ to $S$
  • $\text{Extract_min}()$ – remove the minimal element in $S$ and return it

We can implement with a heap the above methods in $O(\log n)$, however, we're looking at a bigger picture, a general case that we have no guarantee that $M$ is indeed a heap. Prove that no matter what kind of data structure $M$ is, that at least one of the methods that $M$ supports must take $\Omega(\log n )$.

My solution:

Each sorting algorithm that is based on comparisons must take at the worst case at least $\Omega(n\log n)$ – we'll prove that using a decision tree: if we look at any given algorithm that is based on comparisons, as a binary tree where each vertex is a compare-method between 2 elements:

  • if the first is bigger than the second element – we'll go to the left child
  • if the second is bigger than the first element – we'll go to the right child

At the end, we'll have $n!$ leaves that are the options for sorting the elements.

The height of the tree is $h$, then:

$$2^h \ge n! \quad\Longrightarrow\quad \log(2^h) >= \log(n!) \quad\Longrightarrow\quad h \ge \log(n!) \quad\Longrightarrow\quad h = \Omega(n \log n)$$

Then, if we have a $\Omega(n \log n)$ worst case for $n$ elements, then we have a $\Omega(\log n)$ for a single element.

I'm not sure regarding this solution, so I'd appreciate for corrections or anything else you can come up with.

$\endgroup$
  • $\begingroup$ What you wrote make sense. If both operations are "fast" then you would be able to use the database to sort $n$ elements in less than $O(n \log n)$ which is a contradiction. $\endgroup$ – Ran G. Jun 23 '12 at 13:47
  • $\begingroup$ The title “Prove that exists a data structure that supports Extract_min() and Insert(x) in Ω(logn)?” does not match the question. $\endgroup$ – Tsuyoshi Ito Jun 23 '12 at 14:38
  • 1
    $\begingroup$ Each algorithm that is based on comparisons must take at the worst case at least Ω(nlogn), this doesn't make sense, Each algorithm for doing what?for extract_min? inserting? what? $\endgroup$ – user742 Jun 23 '12 at 14:49
  • $\begingroup$ If those are the only two methods that need to be supported could they not both have constant time? Consider if M just tracks the current minimum. Insert compares to the minimum, and Extract_min returns it. $\endgroup$ – edA-qa mort-ora-y Jun 24 '12 at 4:38
  • $\begingroup$ @edA-qamort-ora-y: And what about the second-smallest element? The runtime bound on Extract_min has to apply for that one, too. $\endgroup$ – Raphael Jun 26 '12 at 12:41
12
$\begingroup$

I don't think your proof is valid, because it only considers trees, and a certain type of trees at that. If there were an algorithm with a smaller lower bound for what you describe, we'd have a sorting algorithm faster than $\Omega(n \log n)$ no matter which of the two operations is $\log n$. So the problem reduces to proving that sorting cannot be faster than $\Omega(n \log n)$, which is a classical proof that you can find online.

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