\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts}
\begin{document}
\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'10)} \\[1ex]
{Prof.~Erik Demaine \qquad Dr.\ Andr\'e Schulz \qquad TA: Aleksandar Zlateski} \\[2ex]
\framebox{Problem 5} \quad {Sample Solutions}
\end{center}
\section*{\boldmath Cartesian trees in linear time.}
We will add the elements according to their order in $A$. If the current element $x$ is greater
than the previously added one, we just add it as its right child. Otherwise, we walk up the
three until we find an element that is smaller then the current one. We then attach $x$ as
its right child, and attach it's previous right child as $x$'s left child.
It is clear that with every step we make towards the root we reduce the path from the
last element to the root by one. Having total of $n$ elements, the maximum number of steps
we make towards the root is also $n$. Therefore, the amortized time of insertion is $O(1)$.
\section*{\boldmath Space requirements for integer data structures.}
\subsection*{1.}
Solving the reccurence on the size of a vEB tree for the universe $u$ we get:
$$C(u) = (\sqrt{u}+1)C(\sqrt{u}) + O(1)$$
We get $C(u) = O(u)$
\subsection*{2.}
Conside the worst case, in which the prefixes diverge as early as possible. In each level $i$
there are $2^i$ different prefixes. We reach $n$ different prefixes at level $\log n$, at which
each table can take up to $O(n)$ space.
Therefore our new bound is $O(n(\log{\frac{u}{n}} -1))$
\end{document}