# General Proof on Potential Method and Amortized Analysis

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)$$

• 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|))$ Jun 2 at 15:23
• 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).
– jugc
Jun 2 at 15:30
• Where did you encounter this task? Can you credit the original source? This may help us understand exactly what is being asked.
– D.W.
Jun 2 at 17:13
• What is $|T|$? Does it relate to $d_t$?
– D.W.
Jun 2 at 17:15
• 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).
– jugc
Jun 2 at 18:25