What time complexity is more significant? [closed]
-
06-11-2019 - |
Question
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?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange