MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.