Suppose there are $\lceil\log n\rceil$ sorted lists of $\lceil\frac{n}{\log n}\rceil$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)

  1. $O(n \log \log n)$

  2. $θ(n \log n)$

  3. $Ω(n \log n)$

  4. $Ω(n^{\frac{3}{2}})$

My approach:

I know complexity of heap sort is $O(n \log n)$. But little bit confused form where to start.

  • $\begingroup$ A heap data structure can be used for heap sort, but it is actually a priority queue. You insert elements into the heap, and then you can extract them in order of "priority". For example, a max-heap would return the largest element first and a min-heap would return the smallest element first. As an additional hint, you're given a bunch of already-sorted lists. What sort algorithm would you consider first? $\endgroup$ – Pseudonym Feb 5 '15 at 22:14

Hint: Try to merge the lists in the correct way, using the fact that merging lists of size $m_1,m_2$ costs $O(m_1+m_2)$. If you do this correctly, you will obtain an $O(n\log\log n)$ algorithm.

We can also get a matching lower bound. The number of possible answers is $$ \begin{align*} \frac{n!}{(n/\log n)!^{\log n}} &\sim \frac{\sqrt{2\pi n}(n/e)^n}{\sqrt{2\pi n/\log n}^{\log n}(n/e\log n)^n} \\ &\sim \frac{(\log n)^{\log n}}{\sqrt{2\pi n}^{\log n-1}}(\log n)^n. \end{align*} $$ The dominant term here is $(\log n)^n = \exp(n\log\log n)$, and we get an $\Omega(n\log\log n)$ lower bound in the decision tree model.

  • $\begingroup$ Just as a comment, the $\Omega(n \log \log n)$ lower bound does assume that all of the elements are distinct. $\endgroup$ – Pseudonym Feb 6 '15 at 0:21
  • 1
    $\begingroup$ Right, and we are free to assume that, since the algorithm has to work even if all elements are distinct. $\endgroup$ – Yuval Filmus Feb 6 '15 at 0:22
  • $\begingroup$ @YuvalFilmus How do you come up with $\frac{n!}{(n/\log n)!^{\log n}}$. Could you please elaborate. $\endgroup$ – Atinesh Feb 6 '15 at 10:00
  • $\begingroup$ Divide $\{1,\ldots,n\}$ into $\log n$ equal parts $B_1,\ldots,b_{\log n}$. This is the number of permutations of $\{1,\ldots,n\}$ in which the elements of each $B_i$ appear in order. $\endgroup$ – Yuval Filmus Feb 6 '15 at 14:03

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.