\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts}
\usepackage{clrscode}
\begin{document}
\begin{center} \Large
{\scshape 6.897 Advanced Data Structures (Spring'05)} \\[1ex]
{Prof.~Erik Demaine \quad\quad TA: Mihai P\v{a}tra\c{s}cu} \\[2ex]
\framebox{Problem 3 -- Solution}
\end{center}
We hold two data structures $D_1$ and $D_2$. For the first
$\frac{m}{2}$ operations, we simulate all operations on both $D_1$ and
$D_2$, taking time $2t$ per operation. After this, the data structures
will have a phase shift of $\frac{m}{2}$ operations.
During the next $\frac{m}{2}$ operations, we use $D_1$ as the main
data structure. We run operations on it, and obtain the relevant
results. During this time, we perform a global rebuilding on $D_2$,
followed by a simulation of all the $\frac{m}{2}$ operations which it
missed (but we stored them somewhere for later use). This takes time
$mt + \frac{m}{2}t = \frac{3}{2} mt$. We simulate $3t$ steps of this
process for every operation run on $D_1$. Thus, the worst-case running
time is $4t$ per operation.
At the end of this, $D_2$ has caught up with all past operations, and
it can handle new operations as the main data structure. At this time,
$D_1$ must go into global rebuilding, so it becomes the secondary data
structure. After $\frac{m}{2}$ operations, we switch roles again. In
the steady state, a data structure has a global rebuilding after
exactly $m$ operations: the first $\frac{m}{2}$ are not in real time
(they are executed while it is catching up), and the next
$\frac{m}{2}$ use it as the main data structure.
\end{document}