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.
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$Insert
compares to the minimum, andExtract_min
returns it. $\endgroup$Extract_min
has to apply for that one, too. $\endgroup$