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$
  • 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.