3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – Tsuyoshi Ito
    Commented Jul 24, 2011 at 15:13
  • 1
    $\begingroup$ 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). $\endgroup$
    – David Harris
    Commented Jul 24, 2011 at 15:18

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .