Accounting method (computer science)

<p>In the field of <a href="/facts/Analysis_of_algorithms/pStoBgBn">analysis of algorithms</a> in <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the accounting method is a method of <a href="/facts/Amortized_analysis/9fFYenJz">amortized analysis</a> based on <a href="/facts/Accounting/sHznDY3V">accounting</a>.  The accounting method often gives a more intuitive account of the amortized cost of an operation than either <a href="/facts/Aggregate_analysis/9fFYenJz">aggregate analysis</a> or the <a href="/facts/Potential_method/NQUvGTbg">potential method</a>.  Note, however, that this does not guarantee such analysis will be immediately obvious; often, choosing the correct parameters for the accounting method requires as much knowledge of the problem and the complexity bounds one is attempting to prove as the other two methods.
</p><p>The accounting method is most naturally suited for proving an <a href="/facts/Big_O_notation/weFFjSWg">O</a>(1) bound on time.  The method as explained here is for proving such a bound.
</p>

Accounting method (computer science) open-in-new

Accounting method (computer science)