Zig Case

We need to show that $\hat{c}_t + \Phi(D_{t-1}) - \Phi(D_t) \ge c_t$.

Here, we'll take $\hat{c}_t = 3(\log s_{t}(x)- \log s_{t-1}(x))+1$. The actual cost ct = 1. Why?

\begin{eqnarraystar} \lefteqn{\hat{c}_t + \Phi(D_{t-1}) - \Phi(D_t)}\\ &=& 3(\lo... ...\ &\ge& 2(\log s_{t}(x)- \log s_{t-1}(x)) + 1\\ &\ge& 1 = c_t.\end{eqnarraystar}

next up previous
Next: Zig-Zig Case Up: ANALYSIS OF SPLAY TREES Previous: Case Setup