\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts}

\newcommand{\proc}[1] {\textnormal{\scshape#1}}
\newcommand{\poly} {\mathrm{poly}}
\newcommand{\eps}  {\varepsilon}

\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 5} \quad {\em Due: Monday, Mar.~7}
\end{center}

\noindent
{\bf Timing:} This problem depends on Thursday's lecture.

\bigskip

Consider the predecessor problem. Let $t_q$ be the amortized time for
one predecessor query, $t_u$ be the amortized time for one update
(insert or delete), and $S$ be the space of the data structure.

In class, we discussed the idea of bucketing elements, and using a
balanced binary search tree inside each bucket. This idea shows that
we can convert a solution with parameters
\[ \Big[ t_q = O(\lg w),\: t_u = O(\poly(w)),\: 
  S = O(n \cdot \poly(w)) \Big] \]
into a solution with parameters:
\[ \Big[ t_q = O(\lg w),\: t_u = O(\lg w),\: S = O(n) \Big] \]

This problem achieves an even more impressive result when all bounds
are in terms of $n$.

\bigskip

\noindent
{\bf Prove the following:} Given a data structure for the predecessor
problem with parameters 
\[ \Big[ t_q = O(T),\: t_u = O(\poly(n)),\: S = O(\poly(n)) \Big] \]
one can construct a data structure with parameters 
\[ \Big[ t_q = O(T\cdot \lg\lg n),\: 
  t_u = O(T\cdot \lg\lg n),\: S=O(n) \Big] \]
Furthermore, if $T = \lg^{\alpha} n$, where $\alpha>0$ is a
constant, the new data structure has parameters
\[ \Big[ t_q = O(T),\: t_u = O(T),\: S=O(n) \Big] \]

\medskip \noindent
{\bf Note:} You need only discuss insertions. Deletions can be
handled, but they are a bit trickier.

\bigskip

Thus, for any polynomial space and update times, we can reduce the
space to linear, and the update to match the query time, while only
blowing up the query complexity by $O(\lg\lg n)$. If the query
complexity is not too low, i.e.~it is $\lg^{\Omega(1)} n$, we don't
even change the query complexity at all! So for bounds in terms of
$n$, space and update times essentially don't matter.

\medskip

\noindent
{\bf Hint:} Consider a tree with branching factor $n^{\eps}$.

\end{document}
