0
$\begingroup$

A certain algorithm executes $n$ operations of three types: insert, delete, and find. We know that $n/10$ of the operations are inserts, and the rest are deletes and finds.

You are given two implementations of the algorithm. The first one implements insert in worst case $\Theta(n)$, and the amortized cost of every operation (including insert) is $\Theta(1)$. The second implementation implements insert in worst case $\Theta(\log n)$, and the amortized cost of every operation (including insert) is $\Theta(\log n)$.

Which implementation would you recommend, and why?

$\endgroup$

closed as unclear what you're asking by Evil, xskxzr, Yuval Filmus, Juho, D.W. Sep 13 at 18:23

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ In order to recommend an implementation, you have to tell us when is one implementation preferred over another for you. It's hard to compare different choices without any criteria for comparison. $\endgroup$ – Yuval Filmus Sep 12 at 6:57
0
$\begingroup$

You are asking for a practical answer, so you need a practical problem.

State your practical problem. Then examine what would be the effect of using one implementation vs. the other. Based on this examination, you can choose which implementation is more acceptable to you.

$\endgroup$

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