0
$\begingroup$

In "Introduction to Algorithms" by Cormen et al. the Potential Method is explained. For example, we have the following representation for the amortized costs of the i-th operation with respect to the potential function $\Phi$:

$$\hat{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1})$$

The book also states that for each $i = 1,2,...,n$ we let $c_i$ be the actual cost of the i-th operation.


Question:

My question is, what exactly are the actual costs ($c_i$) of the i-th operation? Are this runtime cost, or how can we think of it? How exactly is this determined/measured? Unfortunately, this point remains unanswered to my mind.

Also interesting is the stack example with the push operation, in the book the cost of $c_i$ is given with 1. This assumption is not justified there, which I find a bit ambiguous (Because otherwise one could have set this arbitrarily high).

For helpful answers/comments I would be very grateful!

$\endgroup$

1 Answer 1

2
$\begingroup$

The value of $c_i$ is the runtime cost of an operation. Understand that in doing analysis you can simplify the assignment of runtime cost by focusing only on important aspects. As for your stack example, they might have simplied things and assume that the cost of a push/pop is based on the number of elements processed, ignoring other factors.

Indeed, you are right that you can assign some other value for the cost of a push by being more detailed. Say assign a value of 2 because you count 1 for inserting the element and 1 for updating the top pointer of the stack. This amount of detail might not be necessary since it does not change the overall analysis.

$\endgroup$

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.