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)
$O(n \log \log n)$
$θ(n \log n)$
$Ω(n \log n)$
$Ω(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.
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.
