\documentclass{article}
\usepackage{float}
\usepackage{hyperref}
\hypersetup{
    pdfborder={0 0 0}
}
\usepackage{graphicx}
\graphicspath{{images/}}

\setlength{\parindent}{0pt}
\setlength{\parskip}{0.6em}
\linespread{1.08}

\title{Outline of EE}
\author{Seungjun Lee}
\date{February 22, 2026}

\begin{document}
\maketitle

\begin{abstract}

    \textbf{Title}:
    When Asymptotic Complexity Fails: An Empirical and Cost-Based Study of Binary and Fibonacci Heaps in Python

    \textbf{RQ}:
    Why does the theoretical asymptotic advantage of Fibonacci heap in Dijkstra’s algorithm not translate into practical runtime improvements in Python implementations?

    \textbf{Category}:
    Computer Science

\end{abstract}

\newpage
\tableofcontents
\newpage

\section{Introduction}

\subsection*{Context}
\begin{itemize}
    \item Dijkstra’s algorithm widely used for shortest path problems
    \item Priority queue choice affects theoretical time complexity
    \item Pure Dijkstra: $O(E+ V^2)$
    \item Binary heap: $O(E \log V)$
    \item Fibonacci heap: $O(E + V \log V)$
    \item Theoretical advantage not clearly observed in practical implementations
\end{itemize}

\subsection*{Outline of argument}
\begin{itemize}
    \item Graph structure influences decrease-key frequency
    \item Decrease-key frequency determines theoretical advantage
    \item Empirical runtime does not reflect the theory
    \item Operation level cost explains the gap between the thoery and reality
\end{itemize}

\subsection*{Scope}
\begin{itemize}
    \item Python implementation only
    \item Synthetic directed graphs (using outdegree-based generation)
    \item Lognormal edge weight distribution
    \item Nodes: 2000--16000, density: 0.00015--0.0384, stds: 1000--16000, trials: 200
    \item Single-source single-target shortest path
\end{itemize}

\subsection*{Worthiness}
\begin{itemize}
    \item Evaluates limits of asymptotic complexity in practice
    \item Provides empirical basis for heap selection
    \item Bridges theory and implementation level cost analysis
\end{itemize}

\section{Theoretical Framework}

\begin{itemize}
    \item Formal runtime models:
          \begin{itemize}
              \item $T_B = c_1 E \log V$
              \item $T_F = c_2 E + c_3 V \log V$
          \end{itemize}
    \item Role of decrease-key in Dijkstra
    \item Relation between relax\_success and decrease-key calls
    \item Theoretical crossover condition:
          \[
              T_F < T_B
          \]
\end{itemize}

\section{Methodology}

\subsection*{Development}
\begin{itemize}
    \item Real-world road dataset used to estimate distribution of real-world data
    \item Lognormal parameters derived from real data
    \item Synthetic graph generation with various nodes, density, std
    \item Measurement metrics:
          \begin{itemize}
              \item reached
              \item extract\_min\_calls
              \item relax\_attempts
              \item relax\_success
              \item relax\_success\_ratio
              \item runtime
          \end{itemize}
\end{itemize}

\subsection*{Evidence}
\begin{itemize}
    \item Experimental configuration
          \begin{verbatim}
python -V
Python 3.12.12

pip -V
pip 26.0.1

python -c "import platform; print(platform.platform())"
Linux-6.8.12-17-pve-x86_64-with-glibc2.41

lscpu | head
Architecture:               x86_64
CPU op-mode(s):             32-bit, 64-bit
Address sizes:              48 bits physical, 48 bits virtual
Byte Order:                 Little Endian
CPU(s):                     16
On-line CPU(s) list:        1-3,8
Off-line CPU(s) list:       0,4-7,9-15
Vendor ID:                  AuthenticAMD
Model name:                 AMD Ryzen 7 7700 8-Core Processor
CPU family:                 25
    \end{verbatim}
\end{itemize}

\subsection*{Analysis}
\begin{itemize}
    \item Justification of parameter intervals
    \item Retain stability by 200 trials
\end{itemize}

\subsection*{Connection}
\begin{itemize}
    \item Method is the fundament of runtime investigation
\end{itemize}

\section{Real Data Analysis}

\subsection*{Development}
\begin{itemize}
    \item Get real data from DIMACS
    \item Extraction of edge weight distribution
    \item Calculation of mean and std
\end{itemize}

\subsection*{Evidence}
\begin{itemize}
    \item Edge weight distribition
          \begin{figure}[H]
              \centering
              \includegraphics[width=0.7\textwidth]{hist_original.png}
          \end{figure}
          \begin{figure}[H]
              \centering
              \includegraphics[width=0.7\textwidth]{hist_log.png}
          \end{figure}
    \item Summary statistics tableofcontents
          \begin{table}[H]
              \centering
              \begin{tabular}{ll}
                  \hline
                  Key         & Value    \\ \hline
                  Total edges & 58333344 \\
                  Mean        & 2950.322 \\
                  Std         & 4071.694 \\
                  Min         & 1        \\
                  Max         & 368855   \\ \hline
              \end{tabular}
          \end{table}
\end{itemize}

\subsection*{Analysis}
\begin{itemize}
    \item Lognormal approximation calculation
    \item Justification of synthetic distribution parameters
\end{itemize}

\subsection*{Connection}
\begin{itemize}
    \item Synthetic data is based on real-world data
\end{itemize}

\section{Relationship between variables}

\subsection*{Development}
\begin{itemize}
    \item Density vs relax\_attempts
    \item Sigma vs relax\_success\_ratio
    \item Decrease-key vs speedup
\end{itemize}

\subsection*{Evidence}
\begin{itemize}
    \item Density vs relax\_attempts plot
          \begin{figure}[H]
              \centering
              \includegraphics[width=0.7\textwidth]{density_vs_relax_attempts.png}
          \end{figure}
    \item Sigma vs relax\_success\_ratio platform
          \begin{figure}[H]
              \centering
              \includegraphics[width=0.7\textwidth]{sigma_vs_relax_ratio.png}
          \end{figure}
    \item Decrease-key vs speedup correlation
          \begin{figure}[H]
              \centering
              \includegraphics[width=0.7\textwidth]{speedup_corr.png}
          \end{figure}
\end{itemize}

\subsection*{Analysis}
\begin{itemize}
    \item Density increases relax attempts nearly linearly
    \item Higher variance increases relax\_success ratio
    \item Speedup weakly correlated with decrease-key frequency
\end{itemize}

\subsection*{Connection}
\begin{itemize}
    \item Structural conditions necessary but insufficient for crossover
\end{itemize}

\section{Runtime}

\subsection*{Development}
\begin{itemize}
    \item Multiple linear regression of runtime
    \item Operation level cost estimation
\end{itemize}

\subsection*{Evidence}
\begin{itemize}
    \item Regression summary table
          \begin{table}[H]
              \small
              \centering
              \begin{tabular}{llllllll}
                  \hline
                  algorithm & intercept & $coef_{add}$  & $coef_{extract}$ & $coef_{relax}$ & $coef_{decrease}$ \\ \hline
                  binary    & 0.000492  & -3.496595e-07 & 3.259253e-07     & 9.095429e-08   & 1.702164e-07      \\
                  fibonacci & -0.001191 & 7.446706e-07  & 3.938917e-07     & 9.333419e-08   & 1.504052e-06      \\ \hline
              \end{tabular}
          \end{table}
    \item $R^2$ comparison between models
          \begin{table}[H]
              \centering
              \begin{tabular}{lll}
                  \hline
                  algorithm & $r_2$    & $n_{samples}$ \\ \hline
                  binary    & 0.980930 & 54801         \\
                  fibonacci & 0.980877 & 54801         \\ \hline
              \end{tabular}
          \end{table}
\end{itemize}

\subsection*{Analysis}
\begin{itemize}
    \item Fibonacci decrease-key cost significantly larger in Python
    \item Constant factors dominate asymptotic differences
\end{itemize}

\subsection*{Connection}
\begin{itemize}
    \item Explains absence of empirical speedup
\end{itemize}

\section{Deriving the Crossover Condition}

\subsection*{Development}
\begin{itemize}
    \item Substitute empirical coefficients into:
          \[
              T_F < T_B
          \]
\end{itemize}

\subsection*{Evidence}
\begin{itemize}
    \item Derived inequality expression
\end{itemize}

\subsection*{Analysis}
\begin{itemize}
    \item Required conditions exceed practical graph scale
    \item Python constant overhead prevents crossover
\end{itemize}

\subsection*{Connection}
\begin{itemize}
    \item Theoretical superiority does not always linked to practical improvement
\end{itemize}

\section{Conclusion}

\subsection*{Conclusion}
\begin{itemize}
    \item Fibonacci heap does not outperform Binary heap in Python
    \item Operation level costs dominate asymptotic complexity
    \item Crossover condition impractical under tested environment
\end{itemize}

\subsection*{Limitation \& Evaulation}
\begin{itemize}
    \item Python-only implementation
    \item Synthetic graph model assumptions
    \item No low-level memory/cache analysis
\end{itemize}

\subsection*{Summarize main points}
\begin{itemize}
    \item Graph structure affects decrease-key frequency
    \item Empirical runtime does not follow asymptotic expectation
    \item Constant factors determine real-world performance
\end{itemize}

\end{document}