\documentclass[10pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{fullpage}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

\newenvironment{proof}{\noindent {\bf Proof.}}%
                      {$\Box$}

\newcommand{\eli}{\>}


\begin{document}


\title{TIRGUL 4 in Data Structure -- solution of last question -- draft\\ 
\small (Remember that these notes are unchecked and spelling
mistakes and inaccuracies may be plentiful) \normalsize}

\author{Elad Verbin}

\maketitle

\underline{Exercise:} Prove that a sequence of $m$ insertions into
an initially-empty 2-4 tree costs a total of $O(m)$ time, assuming
that at each insertion you are given a pointer to the location
where the item should be inserted.

\underline{Proof:} Using the potential method. We use the
potential $\Phi$ which is equal to the number of nodes of degree
4. (many other potential functions would also work). We have to
prove two things: (1) That the potential is initially equal to $0$
and is always nonnegative; and (2) That for any operation $op$,
$cost(op)+\Delta \Phi \le O(1)$. (1) is obvious. Let us prove (2).
Every insertion operation costs $O(1)+k$ where $k$ is the number
of SPLIT operations that are performed. Every split causes a node
of degree 4 to split into a node of degree 2 and a node of degree
3. Therefore, every SPLIT operation decreases the potential by 1.
This is true except for the first SPLIT, which is on a leaf and
therefore splits a node with degree 0 to two nodes with degree 0,
and for the last SPLIT, which indeed splits a node $v$ of degree 4
to two nodes of degrees 2 and 3, but the father may change to be
of degree 4 which may increase the potential back by 1. But since
these are only the first and last SPLIT, all other SPLITs decrease
the potential by 1, and so $\Delta \Phi \le -(k-2)$. From this it
follows that, indeed, $cost(op)+\Delta \Phi = O(1)$.

(I will review this in the beginning of the next TIRGUL).


\end{document}

