Let $T$ be an arbitrary data structure for a dynamic set. For every state T of $T$, let $d_t \in \mathbb{N}$. Observe two Operations $O_1, O_2$ on $T$ whose runtimes are proportional to $d_t$ and $O_1$ does not change the structure of $T$. Let $f\colon \mathbb{N} \mapsto \mathbb{N} $. Suppose there exists a potential $\phi$ for which $O_2$ has an amortised complexity in $O(f(|T|))$. Show that there exists a potential $\phi'$ for which $O_1$ and $O_2$ together have an amortised complexity in $O(f(|T|))$.

I'm not sure how one would go about proving this Statement maybe because of the general nature or the formalism of the question but I'm not getting anywhere. I would be very grateful for any hints/explanations on how to approach this question.

Edit: What I think might be the Solution:

We know the amortized complexity of $O_2$ is given by $A_2=x_2*d_T + \phi(T´) - \phi(T)$

To show that $A_{1+2} \in O(f(|T|))$ we need to define a potential $\phi´$ such that
$A_{1+2} = x_1*d_t + x_2 *d_T + \phi´(T´) - \phi´(T) = c*(x_2*d_T + \phi(T´) - \phi(T))$ for some constant $c$.

Which should work for $\phi´(T) = \frac{x_1 +x_2}{x_2}*\phi(T)$

  • $\begingroup$ What constraint are you given on $O_1$? If there isnt a constraint, then $O_1$ can by itself take time much larger than $O(f(|T|))$ $\endgroup$
    – nir shahar
    Jun 2, 2021 at 15:23
  • $\begingroup$ Only that $O_1$ runtime is proportional to $d_t$, and that it does not change the Structure of $T$. As a bit of context we are doing some stuff on Splay Trees and if I´m correct one can think of $O1$ as being a standard BST Search Operation and $O_2$ as the Splay operation (as in en.wikipedia.org/wiki/Splay_tree). $\endgroup$
    – jugc
    Jun 2, 2021 at 15:30
  • $\begingroup$ Where did you encounter this task? Can you credit the original source? This may help us understand exactly what is being asked. $\endgroup$
    – D.W.
    Jun 2, 2021 at 17:13
  • $\begingroup$ What is $|T|$? Does it relate to $d_t$? $\endgroup$
    – D.W.
    Jun 2, 2021 at 17:15
  • $\begingroup$ It is the number of Elements in $T$ for example for a Binary Search Tree the number of Nodes. This is a question from my Computer Oriented Mathematics Class, using the Proof of the above statement we are supposed to show that searching for an element in a Splay Tree, with standard BST Search + Splaying at the end, has an amortized complexity in $O(log(n))$ where n is the number of Nodes in the Tree. (Using a suitable potential). $\endgroup$
    – jugc
    Jun 2, 2021 at 18:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.