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

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

\begin{document}

\maketitle

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

\textbf{Statement:} Inserting into an N-way splay tree with $n$ nodes takes $O(\log n)$ amortized time.

\section{Proof}

\begin{enumerate}
    \item Find insertion point: $O(\log n)$
    \item Insert node: $O(1)$
    \item Splay new node to root: $O(\log n)$ amortized
    \item Adjust branching if needed: $O(1)$ amortized (infrequent)
    \item Total: $O(\log n)$ amortized
\end{enumerate}

\textbf{Conclusion:} N-way splay tree insert has $O(\log n)$ amortized time complexity.

\end{document}
