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.