0
$\begingroup$

If you have a dynamic array where the size $s$ becomes $4s$ when you fill the array and there are no delete operations. How much do you spend per insert?

I am asking because when the size doubles, you only spend 3 dollars per insert (based on this analysis). But when you make the size 4 times bigger, then for some of the inserts you would need to spend 3\$ and for the rest you spend 2$?

Is this right? Or do we always need to spend the same amount? And if there is extra we just store it in the bank?

Improve this question
$\endgroup$
2
  • $\begingroup$ How much you spend depends on you. I wish they'd teach amortized analysis without mentioning money. The idea is that although each operation could be $\Omega(f(n))$, if you run $n$ operations then it total the time is $O(ng(n))$, where $g(n) = o(f(n))$. Charging is just a proof method, and it uses monetary transfers only because it was invented in the US. $\endgroup$
    – Yuval Filmus
    Commented Mar 11, 2013 at 1:55
  • $\begingroup$ Perform the analysis as mentioned here: cs.stackexchange.com/a/10448/4975 $\endgroup$
    – ajmartin
    Commented Mar 11, 2013 at 5:10

0

Reset to default

Browse other questions tagged or ask your own question.