1
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2015 at 22:14

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2015 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$ Feb 6, 2015 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, 2015 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$ Feb 6, 2015 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.