# Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$?

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.

• 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. – Ran G. Jun 23 '12 at 13:47
• The title “Prove that exists a data structure that supports Extract_min() and Insert(x) in Ω(logn)?” does not match the question. – Tsuyoshi Ito Jun 23 '12 at 14:38
• 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? – user742 Jun 23 '12 at 14:49
• 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. – edA-qa mort-ora-y Jun 24 '12 at 4:38
• @edA-qamort-ora-y: And what about the second-smallest element? The runtime bound on Extract_min has to apply for that one, too. – Raphael Jun 26 '12 at 12:41

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.