1
$\begingroup$

For amortized analysis (aggregate method), dynamic table insertion cost can be divided into:

if no expansion, then cost = 1 if we expand the table, then cost = i (if i-1 is an exact power of 2)

then the total cost is total cost

I don't understand how to get 2n from the part that I circle below why

$\endgroup$

1 Answer 1

0
$\begingroup$

It should be an inequality, using the formula for the sum of a geometric series: $$ \sum_{j=0}^m 2^j = 2^{m+1} - 1. $$ Substituting $m = \lg n$ gives $$ \sum_{j=0}^{\lg n} 2^j = 2^{\lg n+1} - 1 = 2n-1. $$

$\endgroup$
1
  • $\begingroup$ got it, thank you $\endgroup$ Nov 27, 2022 at 11:27

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.