1
$\begingroup$

I've started taking a data structure course and we are currently learning about different data structures. We also learned when to increase the capacity of an array by creating another array with double the size of the original one.

The proof used to demonstrate this was a credit-debit proof where each operations has a cost. ex: doubling an array cost 2 dollars reducing an array by half cost 1 dollar.

I simply don't understand how proof of that type works. Doing a quick online search I haven't find the term credit-debit used to refer to this. Maybe It's not its name? Would be nice if someone could give me some links that explain those proofs.

$\endgroup$
3
$\begingroup$

I believe you are referring to the accounting method for amortized analysis. With these keywords you should be able to find the explanations you are looking for.

$\endgroup$
1
  • 1
    $\begingroup$ thank you for this. $\endgroup$ – BreezeWind Jan 16 '20 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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