Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

One common method for proving that a data structure supports an operation in $O(f(n))$ amortized time is to construct a potential function $\Phi: \mathcal S \rightarrow \mathbf R^{+}$, which associates every state of the data structure with a positive real number, such that for any operation $\Delta \Phi + \text{actual time} = O(f(n))$.

Is the converse true, i.e. that for any data structure in amortized time $O(f(n))$ there is a potential function $\Phi$ which witnesses this fact (and has this amortized-time property) ? If not, are there are any non-artifical counterexamples?

share|improve this question
    
What prevents you from defining Φ as (the sum of amortized times of the operations performed so far) minus (the sum of the actual times of the operations performed so far)? –  Tsuyoshi Ito Jul 24 '11 at 15:13
1  
The potential function is supposed to be a function of the state of the data structure. The data structure does not necessarily store enough information in the state (although perhaps it could be modified to store this). –  David Harris Jul 24 '11 at 15:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.