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

Question

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.

Answer 1

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.