# Tight analysis on a custom data structures with Insert and Remove-Min

I have a data structure supporting the operations Insert(X) and Remove-Min(). Remove-Min() is performed in $$O(\sqrt{\log n})$$. And I am supposed to show that the Insert is bounded by $$\Omega(\log n)$$.

I would like to ask how to approach this problem. $$O(\sqrt{\log n})$$ never really occured to me and I do not know how to start.

My attempt was: Since the best possible sorting is in $$O(n \log n)$$ one needs insertion in $$\log n$$ to be able to retrieve the current minimum element in $$O(1)$$. But then, this is not tight enough, plus the element should be removed.

Here is how to sort a list $$a_1,\ldots,a_n$$ using your data structure: insert all elements, and then repeatedly remove the minimum element.
• The square root is a red herring. Any running time which is $o(\log n)$ would have the same effect. Mar 13 at 20:48
• Hmm, but why, I know that $O(\sqrt{\log n}) \nsubseteq O (\log(\sqrt n)) = O(\log n)$. So I do not fill confident that I can take $O(\sqrt{\log n})$ as $O(\log n)$ per se. Mar 13 at 20:54