1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

You take it from here.

$\endgroup$
4
  • $\begingroup$ Hi @Yuval, can you please clarify, I still do not relate this to the square root. $\endgroup$
    – NiRvanA
    Mar 13, 2022 at 20:47
  • $\begingroup$ The square root is a red herring. Any running time which is $o(\log n)$ would have the same effect. $\endgroup$ Mar 13, 2022 at 20:48
  • $\begingroup$ 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. $\endgroup$
    – NiRvanA
    Mar 13, 2022 at 20:54
  • 1
    $\begingroup$ I’m sorry, but you’ll have to take it from here. $\endgroup$ Mar 13, 2022 at 20:55

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.