\subsection{Experimento 3 bis}


\begin{wrapfigure}{L}{0.5\textwidth}
    \includegraphics[width=0.5\textwidth]{pearsonCompleteN2LOGN.png}
    \caption{Semejanza entre los tiempos de ejecución del algoritmo 1 y la función $n^2 log(n)$.}
    \label{fig:pearsonN2logN}
\end{wrapfigure}

\paragraph{Contrastación de la complejidad teórica en la empiria: } El tiempo de ejecución del algoritmo de Kruskal para grafos completos es $\mathcal{O}(n^2log(n))$.

\medskip

Realizamos un diagrama de Pearson contrastando los tiempos de ejecución de los grafos completos con una variable aleatoria con distribucion normal y media $n^2log(n)$. Se lo puede ver en la figura \ref{fig:pearsonN2logN}.

\paragraph{Observaciones:} El coeficiente de Pearson es 1 con un p-value suficientemente pequeño como para \textbf{no poder rechazar la hióotesis} de que la complejidad teórica se condice con los resultados empíricos.

¿Sucederá lo mismo para los grafos que eran árboles? Como el sort de Kruskal se realiza sobre todas los ejes y en ese caso la cantidad de ejes no era $\mathcal{O}(n^2)$ sino $\mathcal{O}(n)$, entonces lo esperable es que la complejidad no sea similar a $\mathcal{O}(n^2log(n)$ sino más bien $\mathcal{O}(nlog(n)$.

Veamos el diagrama de Pearson para estas complejidades y los tiempos de ejecución en árboles:

\addvspace{1.5cm}

\begin{figure}[h!]
    \begin{subfigure}{0.5\textwidth}
        \includegraphics[width=1.0\linewidth]{pearsonTreeN2LOGN.png}
        \caption{Grafos completos}
    \end{subfigure}
    \begin{subfigure}{0.5\textwidth}
        \includegraphics[width=1.0\linewidth]{pearsonTreeNLOGN.png}
        \caption{Árboles}
    \end{subfigure}
    \caption{Similitud entre la complejidad empírica y la teórica para grafos con distintas densidades}
    \label{fig:pearsontrees}
\end{figure}

Como se puede ver, para árboles, los tiempos de ejecución se asimilan más bien a una complejidad $\mathcal{O}(nlog(n)$, lo cual se condice con lo que supusimos. Como el sort de los ejes domina la complejidad de Kruskal, variar la cantidad de ejes sobre los que se hace el sort hace variar la complejidad teórica y esto se refleja en la empiria.