\documentclass[11pt]{article}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{geometry}
\geometry{margin=1in}

\title{N-Way Splay Tree Space Complexity Proof}
\author{Shyamal Suhana Chandra}
\date{Copyright (C) 2025}

\begin{document}

\maketitle

\section{Theorem: N-Way Splay Tree Space Complexity}

\textbf{Statement:} An N-way splay tree with $n$ nodes uses $O(n)$ space.

\section{Proof}

Each node stores:
\begin{itemize}
    \item 1 key
    \item 1 value
    \item At most $\text{maxChildren}$ pointers to children
\end{itemize}

Number of nodes: $n$

Total pointers: at most $n \times \text{maxChildren}$

\subsection{Worst Case Analysis}

In worst case, $\text{maxChildren} = O(\sqrt{n})$ (by design constraint):
\begin{align}
\text{Total space} &= n \text{ keys} + n \text{ values} + n \times O(\sqrt{n}) \text{ pointers} \\
&= O(n) + O(n) + O(n\sqrt{n}) \\
&= O(n\sqrt{n})
\end{align}

\subsection{Average Case Analysis}

However, with dynamic branching adjustment:
\begin{itemize}
    \item Average branching factor is $O(1)$
    \item Most nodes have constant number of children
    \item Only occasional nodes require higher branching
\end{itemize}

With dynamic adjustment, amortized space:
\begin{align}
\text{Amortized space} &= n \text{ keys} + n \text{ values} + n \times O(1) \text{ pointers} \\
&= O(n) + O(n) + O(n) \\
&= O(n)
\end{align}

\textbf{Conclusion:} N-way splay tree has $O(n)$ average space complexity with dynamic branching, and $O(n\sqrt{n})$ worst-case space complexity.

\section{Tighter Bound}

With optimal dynamic adjustment strategy:
\begin{itemize}
    \item Branching factor adapts to access patterns
    \item Frequently accessed subtrees may have higher branching
    \item Average case: $O(n)$ space
    \item Worst case: $O(n\sqrt{n})$ space (rare)
\end{itemize}

In practice, the average branching factor remains small, giving $O(n)$ space complexity.

\end{document}
