complexity.tex

\newpage
\part{Complejidad en Tiempo}
\setcounter{section}{0}

Se conoce ya que un algoritmo es una secuencia finita de instrucciones, cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo finito. Así, un programa es un algoritmo expresado en un lenguaje de programación específico. Entonces, pueden existir diversos programas para resolver un mismo problema. 

Tener un mecanismo que permita seleccionar qué programa es ``mejor" que otro sería ideal para lograr los resultados adecuados. Entre dichos mecanismos están los criterios de evaluación de un programa como la eficiencia, portabilidad, legibilidad, eficacia, robustez, entre otros. En esta sección, nos enfocaremos en solo el criterio relacionado con la eficiencia del programa para el análisis de la complejidad de un programa (uso de recursos del computador).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Definiciones}

El análisis de algoritmos provee estimaciones teóricas para los recursos que necesita cualquier algoritmo y se basan en criterios como: eficiencia, portabilidad, eficacia y robustez. El análisis de complejidad está relacionado con la eficiencia del programa. La eficiencia mide el uso de los recursos del computador por un algoritmo tal como el tiempo de cálculo para ejecutar las operaciones (complejidad en tiempo) y el espacio de memoria para contener y manipular el programa más los datos (complejidad en espacio). Así, el objetivo del análisis de complejidad es cuantificar las medidas físicas en  tiempo de ejecución y espacio de memoria para comparar distintos algoritmos que resuelven un mismo problema.

El tiempo de ejecución depende de diversos factores como:
\begin{itemize}
\item Los datos de entrada del programa
\item La calidad del código objeto generado por el compilador
\item La naturaleza y rapidez de las instrucciones de máquina utilizadas
\item La complejidad en tiempo del algoritmo base del programa
\end{itemize}

Hay dos estudios posibles sobre el tiempo de ejecución:

\begin{enumerate}
\item Un estudio que proporciona una medida teórica (a priori), que consiste en obtener una función que acote (por arriba o por abajo) el tiempo de ejecución del algoritmo para unos valores de entrada dados
\item Un estudio que ofrece una medida real (\textit{a posteriori}), consistente en medir el tiempo de ejecución del algoritmo para unos valores de entrada dados y en un
ordenador específico. 
\end{enumerate}

Ambas medidas son importantes: la primera ofrece estimaciones del comportamiento de los algoritmos de forma independiente del computador en donde serán implementados y sin necesidad de ejecutarlos, y la segunda representa las medidas reales del comportamiento del algoritmo.

Dado que la unidad de tiempo a la que debe hacer referencia estos estudios no puede ser expresada en segundos o en otra unidad de tiempo concreta, pues no existe un computador estándar/ideal al que pueda hacer referencia todas las medidas, se denota por $T(n)$ el tiempo de ejecución de un algoritmo para una entrada de tamaño $n$. 

En un análisis teórico de algoritmos, es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada $n$ suficientemente grande, $T(n)$. Teóricamente $T(n)$ debe indicar el número de instrucciones ejecutadas por un
ordenador ``ideal". La notación ``O grande" (\textit{Big O}) es una notación para expresar esto. Por ello, estudiar la complejidad del peor caso, mejor caso, y caso promedio resulta importante en las Ciencias de la Computación:

\begin{enumerate}
\item Peor caso: Consiste Resulta tomar el máximo tiempo en que se ejecuta el algoritmo, entre todas las instancias posibles
\item Mejor caso: Viene dado por el menor tiempo en que se ejecuta el algoritmo
\item Caso promedio: Es la esperanza matemática del tiempo de ejecución del algoritmo para entradas de tamaño $n$
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Operaciones Elementales}

El tiempo $T(n)$ que se mide para un algoritmo, se mide por el número de operaciones elementales que este realiza. Una operación elemental son aquellas que pueden ser acotadas por una constante tales como operaciones aritméticas básicas, asignaciones a variables, invocaciones a unidades de programas, retorno de ellas, etc. Todas estas se pueden contabilizar como una (1) operación elemental. Entonces, el tiempo de ejecución de un algoritmo va a ser una función que mide el número de operaciones elementales que realiza un algoritmo para un tamaño de entrada $n$.

Para un estudio del tiempo de ejecución de un algoritmo en el mejor caso, peor caso y caso promedio veamos un ejemplo concreto. Primero se muestra unas definiciones e inicialización:

\begin{lstlisting}[upquote=true, language=pseudo]
Const Integer N = ...	//número máximo de elementos de un arreglo
Array aValues of Integer [1..N]
fillOrdered(ref aValues, N)	//asigna valores de forma ascendente, i.e. 1,2,3,5,6,9,12, ...
\end{lstlisting}

El algoritmo:

\begin{lstlisting}[upquote=true, language=pseudo, numbers=left]
void Search(ref Array A of Integer [], Integer n, iC)	//se intenta buscar iC en el arreglo
  Integer iJ = 1
  while (A[iJ] < iC and iJ < n) do
    j = j + 1
  end
  if A[iJ] == iC then
    return iJ
  else
    return 0
  end
end
\end{lstlisting}

Nótese que el algoritmo no es la mejor forma para encontrar un elemento en un arreglo ordenado, pero permite ilustrar el número de operaciones elementales que forman la función $T(n)$. Entonces, primero se calcula las operaciones elementales de cada instrucción de la función Search:

\begin{description}
\item [Línea 1:] No se considera como operación elemental. Igual aplica para las líneas 5, 8, 10 y 11.
\item [Línea 2:] Se ejecuta 1 operación elemental de asignación.
\item [Línea 3:] Se ejecuta la condición del while que consta de 2 comparaciones, un acceso al arreglo y un and, para un total de 4 operaciones elementales.
\item [Línea 4:] Se ejecutan 2 operaciones elementales, una asignación y un incremento.
\item [Línea 6:] Se ejecuta un acceso al arreglo y una comparación, para un total de 2 operaciones elementales.
\item [Línea 7:] Se ejecuta 1 operación elemental por el return, cuando la condición es true.
\item [Línea 9:] Se ejecuta 1 operación elemental por el return, cuando la condición es falsa.
\end{description}

En el \textbf{mejor caso}, se ejecuta la línea 2 (1 operación) y solo la primera parte de la condición de la línea 3 (2 operaciones), es decir, la expresión $A[iJ] < iC$ es falsa y se deja de evaluar la condición completa. Para ello, se asume que el operador and es del tipo cortocircuito\footnote{La expresión lógica deja de ser evaluada en el momento que se conoce su valor aunque no hayan sido evaluados todos sus términos.}. Luego, se ejecuta la línea 6 (2 operaciones) y la línea 7 o 9 (1 operación cada una). Como resultado se tiene que la función $T(n)$ es $T(n) = 1 + 2 + 2 + 1 = 6$.

En el \textbf{peor caso}, se ejecuta la línea 2 y la línea 3 se ejecuta $n-1$ veces hasta que se cumpla la segunda parte de la condición. Después se ejecuta la condición de la línea 6 y termina la ejecución con la línea 9. Cada iteración del while está compuesta por las líneas 3 y 4 y una ejecución adicional de la línea 3 que es la salida del ciclo. De esta forma, se tiene a la función $T(n)$ como:

$$T(n) = 1 + ((\sum_{k=1}^{n-1}{(4+2)}) + 4) + 2 + 1 = 6n + 2$$

En el \textbf{caso promedio}, el ciclo se ejecuta un número de veces $k$, donde $0 < k < n-1$. Asumiendo que para cada número $k$ existe una misma probabilidad de suceder, entonces existen $n$ posibilidades (puede que el número no este en el arreglo) y se supone que son equiprobables teniendo una probabilidad asociada a $1/n$. Así, el número promedio de veces que se efectuará el while es:

$$\sum_{k=0}^{n-1}{i\frac{1}{n}} = \frac{n-1}{2}$$

Como resultado se tiene que la función $T(n)$ es:

$$T(n) = 1 + ((\sum_{k=1}^{(n-1)/2}{(4+2)}) + 2) + 2 + 1 = 3n + 3$$

Por defecto se toma el tiempo del peor caso como medida de complejidad $T(n)$ del algoritmo. Por ejemplo, una búsqueda binaria se dice que se ejecuta en un número de pasos proporcional al logaritmo de la longitud de la estructura de datos de la búsqueda, o en $O(log(n))$, dicho coloquialmente como tiempo logarítmico. Es importante destacar que éstos análisis se realizan en una máquina hipotética/ideal.

En la sección \ref{lb:anacompl} se presenta una guía para el cálculo del número de operaciones elementales, función $T(n)$ para sentencias de un algoritmo.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tasas de crecimiento más comunes} \label{lb:tasa}
 
A continuación se describen las funciones más empleadas cuando se calcula la complejidad de algoritmos (ubicadas de forma creciente):

$$1 < log_n < n < n \cdot log_n < n^2 < n^k < ... < 2^n < e^n < k^n < ... < n^n < n! < ...$$

\noindent donde $k$ es una constante y $k > 2$.

A continuación, con el propósito del cálculo del tiempo $T(n)$ de ejecución de un algoritmo la idea es clasificar dichas funciones de forma tal que se puedan comparar. Para ello, se definen clases de equivalencia basadas en notaciones asintóticas para el cálculo en notación ``O".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Notaciones Asintóticas}

Las notaciones asintóticas proporcionan criterios con el fin de agrupar distintas funciones dentro de una misma categoría, sirviendo como herramientas para el cálculo de la complejidad de un algoritmo.

\paragraph{Definición \#1}

Sean $f$ y $g$ dos funciones definidas como un subconjunto de los números reales, $f,g:\mathbb{N} \to \mathbb{R}^+-\{0\}$, se dice que:

$f(x) = O(g(x))$ con $x \in \infty$

$f$ es de orden $g$ si y solo si existe una constante positiva $c \in \mathbb{R}^+$ y $n_0 \in \mathbb{N}$ tal que $\forall n > n_0$ se cumpla que $f(n) < c.g(n)$. La relación $O$ denota una dominancia de funciones en donde la función $f$ está acotada superiormente por un múltiplo de la función $g$. Entonces, la expresión $f=O(g)$ refleja que el orden de crecimiento asintótico de la función $f$ es inferior o igual al de la función $g$. Por ejemplo, tomando $c=5$ y $n_0 = 0$ con $f(n) = 3n^3 + 2n$ se dice que $g(n) = n^3$ acota a $f(n)$ con dichos valores.

Este definición refleja el hecho de que el crecimiento asintótico de las funciones $f$ es como mucho proporcional al de la función $g$. Dicho de otra forma, la tasa de crecimiento de la función $g$ es una
cota superior para las tasas de crecimiento de las funciones $f$.

Algunas propiedades derivadas de la definición anterior se describen a continuación:
\begin{itemize}
\item Si $c \in \mathbb{R}$ y $f:\mathbb{N} \to \mathbb{R}^+ \lbrace 0 \rbrace$, entonces $c.f = O(f)$
\item Si $c \in \mathbb{R}$ y $f:\mathbb{N} \to \mathbb{R}^+ \lbrace 0 \rbrace$, entonces $O(c.f) \equiv O(f)$
\item Si $f_1 = O(g_1)$ $\wedge$ $f_2 = O(g_2)$, entonces $f_1 + f_2 = O(g_1 + g_2)$
\item Si $f_1 = O(g_1)$ $\wedge$ $f_2 = O(g_2)$, entonces $f_1 \cdot f_2 = O(g_1 \cdot g_2)$
\item Si $f_1 = O(g)$ $\wedge$ $f_2 = O(g)$, entonces $f_1 + f_2 = O(g)$
\end{itemize}

\paragraph{Definición \#2}

Sean $f$ y $g$ dos funciones definidas como un subconjunto de los números reales, , $f,g:\mathbb{N} \to \mathbb{R}^+-\{0\}$, se dice que $f$ y $g$ tienen igual orden de crecimiento $f=\Theta(g)$ si y solo si existe $c,d \in \mathbb{R}^+$ y $n_0 \in \mathbb{N}$ tal que $\forall n > n_0$ se cumpla $d.g(n) \le f(n) \le c.g(n)$. Nótese que $\Theta$ es una relación de orden total (reflexiva, transitiva y simétrica) y que $\Theta(g)$ permite acotar a $f$ inferior y superiormente.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\underline{Propiedades}

Además, $\Theta$ satisface las siguientes propiedades:

\begin{itemize}
\item $f, g : \mathbb{N} \to \mathbb{R}^{+}-\{0\}, f = \Theta (g) \Leftrightarrow f = O(g) \wedge g = O(f)$
\item Si $c \in \mathbb{R}^{+}$ y $f: \mathbb{N} \to \mathbb{R}^{+}-\{0\}$, entonces $c \cdot f = \Theta(f)$
\item Si $c \in \mathbb{R}^{+}$ y $f: \mathbb{N} \to \mathbb{R}^{+}-\{0\}$, entonces $\Theta(c \cdot f) = \Theta(f)$
\item Si $f_1 = \Theta(g_1) \wedge f_2 = \Theta(g_2)$, entonces $f_1 + f_2 = \Theta (Max\{g_1, g_2\})$
\item Si $f_1 = \Theta(g_1) \wedge f_2 = \Theta(g_2)$, entonces $f_1 \cdot f_2 = \Theta (g_1 \cdot g_2)$
\item Si $f_1 = \Theta(g) \wedge f_2 = \Theta(g)$, entonces $f_1 + f_2 = \Theta (g)$
\item $(f+g)^k = \Theta(f^k + g^k)$
\end{itemize}

Dada las definiciones explicadas anteriormente, es posible definir que la complejidad $T(n)$ de un algoritmo es de $O(f(n))$ si $T,f:\mathbb{N} \to \mathbb{R}^+-\{0\}$ y $\exists c \in \mathbb{R}^+$ y $n_0 \in \mathbb{N}$ tal que $\forall n > n_0$ se cumpla que $T(n) \le c \cdot f(n)$.

Esto permite definir el análisis de complejidad de algoritmos para:
\begin{itemize}
\item Determinar el comportamiento de un algoritmo en función del tamaño del problema
\item Determinar el incremento del cómputo al incrementar el tamaño
\item Facilitar la comparación entre algoritmos
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Análisis de Complejidad} \label{lb:anacompl}

Para analizar la complejidad $T(n)$ de un algoritmo y determinar que es de complejidad $O(f(n))$ se estudian una serie de reglas que permitirán aplicar las propiedades explicadas en la definición \#1 y \#2.

%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Regla de la Suma}

Para cada instrucción de ejecución de un programa $I_i$, es posible asociarle la complejidad $T_i(n)$, así:

$T_1(n)$ para ejecutar la instrucción $I_1$\\
$T_2(n)$ para ejecutar la instrucción $I_2$\\
$\cdots$ \\
$T_k(n)$ para ejecutar la instrucción $I_k$\\

\noindent con $T_1(n) = O(f(n))$ y $T_2(n) = O(g(n))$

Entonces, la complejidad de la secuencia:
\begin{lstlisting}[upquote=true, language=pseudo, numbers=left]
I1;
I2;
...
Ik;
\end{lstlisting}

\noindent se escribe como $T_1(n) + T_2(n) = O(Max\{f(n), g(n)\})$. Donde la función $Max$ se asocia a clasificar una función de acuerdo a su tasa de crecimiento (ver la sección \ref{lb:tasa}).

%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Regla del Producto}

La regla del producto define que:

$T_1(n) = O(f(n)) \wedge T_2(n) = O(g(n)) \Rightarrow T_1(n) \cdot T_2(n) = O(f(n) \cdot g(n))$

Del mismo modo, se definen las siguientes reglas:
\begin{itemize}
\item $T(n) = c \Rightarrow T(n) = O(1)$
\item $T(n) = c + f(n) \Rightarrow T(n) = O(f(n))$
\item $T(n) = c \cdot f(n) + d \Rightarrow T(n) = O(f(n))$
\item $T_1(n) = O(n^k) \wedge T_2(n) = O(n^{k+1}) \Rightarrow T_1(n) + T_2(n) = O(n^{k+1})$
\item $T(n) = c \cdot n^d \Rightarrow T(n) = O(n^d)$
\item $T(n) = P_k(n) \Rightarrow T(n) = O(n^k)$
\item $T_1(n) = Ln(n) \wedge T_2(n) = n^k \wedge k > 1 \Rightarrow T_1(n) + T_2(n) = O(n^k)$
\item $T_1(n) = r^n \wedge T_2(n) = P_k(n) \wedge r > 1 \Rightarrow T_1(n) + T_2(n) = O(r^n)$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Complejidad de Algoritmos Iterativos} \label{lb:seccomp}

A continuación se presentan una serie de reglas aplicadas al cálculo de instrucciones en un algoritmo.

\begin{description}
\item[Regla 1:] La función T(n) de una instrucción de asignación simple es una constante $c$, así su complejidad en tiempo es $O(1)$. Se asumirá que las operaciones aritméticas simples empleando la sintaxis del lenguaje por sí solas no implican tiempo (en algunas ocasiones se pueden tomar en cuenta en el cálculo).

\item[Regla 2:] La función $T(n$) de una operación de entrada/salida es una constante $c$, así su complejidad en tiempo es $O(1)$. Esta misma regla aplica para operación de lectura/escritura de memoria.

\item[Regla 3:] Una secuencia de $k$ instrucciones cualesquiera $I_1, I_2, \dots , I_k$ con $T_i(n) = O(f_i(n))$, la complejidad total viene dada por:
$$\sum_{i=1}^{k}{T_i(n)}=O(Max\{f_1(n), f_2(n), \dots, f_k(n)\})$$

\item[Regla 4:] Dada la estructura de control (if-then-else):
\begin{lstlisting}[upquote=true, language=pseudo, numbers=left]
if <condición> then		//{T1(n) = O(f(n))}
  <instrucciones 1>		//{T2(n) = O(g(n))}
else
  <instrucciones 2>		//{T3(n) = O(h(n))}
end
\end{lstlisting}
\noindent Su función $T(n)$ se calcula como $T(n) = T_1(n) + Max\{T_2(n), T_3(n)\}$ de esta forma su complejidad es $O(Max\{f(n), Max\{g(n),$ $h(n)\}\})$ $= O(Max\{f(n), g(n), h(n)\})$.

\item[Regla 5:] La función $T(n)$ de una sentencia select donde:
\begin{lstlisting}[upquote=true, language=pseudo, numbers=left]
select
<condicion 1>: <instrucciones 1>	//T1(n) = O(f1(n))
<condicion 2>: <instrucciones 2>	//T2(n) = O(f2(n))
...
<condicion k>: <instrucciones k>	//Tk(n) = O(fk(n))
end
\end{lstlisting}

Se puede escribir como $T(n) = Max\{T_1(n), T_2(n), \dots, T_k(n)\}$ considerando que $T_i(n)$ incluye el cálculo de la evaluación de la condición.

\item[Regla 6:] Dada la estructura de un ciclo while:
\begin{lstlisting}[upquote=true, language=pseudo, numbers=left]
while <condición> do	//{T1(n) = O(f(n))}
  <instrucciones>		//{T2(n) = O(g(n))}
end
\end{lstlisting}
La función $T(n)$ para un ciclo while se puede escribir como: 
$$T(n) = T_1(n) + \sum_{k=1}^{n-1}{(T_1(n) + T_2(n))}$$
Es importante tomar en cuenta que tanto $T_1(n)$ como $T_2(n)$ pueden variar en cada iteración, y por tanto se debe de tomar en cuenta para su cálculo.

Las otras sentencias iterativas (for, do-while, foreach) se pueden representar como un ciclo while. Por ejemplo, el do-while sería:
$$T(n) = \sum_{k=1}^{n}{(T_1(n) + T_2(n))}$$

Para el caso del ciclo for:
\begin{lstlisting}[upquote=true, language=pseudo, numbers=left]
//de forma original
for Integer iI = <inicio> to <final> do
  <instrucciones>
end
//re-escrito como
Integer iI = <inicio>	//{T1(n) = O(f(n))}
while iI <= <final> do	//{T2(n) = O(g(n))}
  <instrucciones>				//{T3(n) = O(h(n))}
  iI = iI + <step>			//{T4(n) = O(i(n))}
end
\end{lstlisting}

La función $T(n)$, de forma detallada, es:

$$T(n) = T_1(n) + T_2(n) + \sum_{k=1}^{<final> - <inicio>}{(T_2(n) + T_3(n) + T_4(n))}$$

Por su parte, el ciclo foreach se comporta igual que el ciclo for con la diferencia que las variables $<inicio>$ y $<final>$ corresponden al rango válido de una colección (i.e. arreglo).

\item[Regla 7:] El tiempo de ejecución de una unidad invocable con parámetros $U(P_1, P_2, \dots, P_k)$ es el tiempo de la invocación de $U$ (1) más el tiempo de evaluación de sus parámetros junto con el tiempo de ejecución del cuerpo de $U$. Así, $T(n) = 1 + T(P_1) + T(P_2) + \dots + T(P_k) + T(U)$. No se toma en cuenta la copia de los valores de los parámetros a la pila de ejecución. Para funciones recursivas se generan ecuaciones de recurrencia.
\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Ejercicios}

A continuación se presenta un serie de ejercicios prácticos acompañados de una breve explicación del cálculo de la complejidad de éstos.

%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Búsqueda Lineal}

El algoritmo de búsqueda lineal consiste en encontrar un valor dentro de un arreglo de valores de dicho tipo. La idea es recorrer desde un extremo del arreglo al otro.

\begin{lstlisting}[upquote=true, language=pseudo, numbers=left]
Const Integer N = ...
Const Integer NOT_FOUND = ...
Array aArr of Integer [1..N]
function LinearSearch(Array aA of Integer [], Integer iN, iX)	//iX es el elemento a buscar
  for Integer iK = 1 to iN do
    if aA[iK] == iX then
      return iK
  end
  return NOT_FOUND
end
//inicialización de aArr con valores
//asignación del valor a buscar en el arreglo y almacenarlo en iX
LinearSearch(aArr, N, iX)
\end{lstlisting}

La línea 11 realiza la invocación a la función LinearSearch la cual implica un tiempo de ejecución a calcular. Según la Regla 7, el tiempo de la invocación a LinearSearch es:
$$T(n) = 1 + T(aA) + T(iN) + T(iX) + T(LinearSearch)$$

Dado que los parámetros no son alguna expresión que requiera un cómputo, se asumirá su tiempo es 1, entonces:

$$T(n) = 4 + T(LinearSearch)$$

Queda calcular el tiempo de la función LinearSearch para determinar el $T(n)$ de la invocación. A partir de este punto \textbf{solamente} se considera para el cálculo de la complejidad de un algoritmo, las instrucciones de dicho algoritmo. Así, cuando se refiera a $T(n)$ será solamente para el conjunto de instrucciones o cuerpo de la función.

Ahora, el primer paso consiste en calcular la cantidad de operaciones elementales de cada i-ésima instrucción para obtener su $T_i(n)$. Particularmente, el tiempo de la unidad invocable es $T(n) = T(CicloFor) + T(Return-Linea9) = T(CicloFor) + 1$. Obteniendo el cálculo del ciclo for, asumiendo que $iN=n$:
\begin{eqnarray*}
T(CicloFor)&=&1 + 1 + \sum_{k=1}^{n - 1}{(1 + T(Lineas 6-7) + 1))}\\
&=&2 + \sum_{k=1}^{n - 1}{1 + (2 + 1) + 1}\\
&=&2 + 5(n - 1)\\
&=&2 + 5n - 5\\
&=&5n - 3
\end{eqnarray*}

Entonces la cantidad de operaciones elementales de la unidad invocable es $T(n) = 5n - 2$. El próximo paso consiste en aplicar las reglas explicadas en la sección \ref{lb:anacompl} para determinar la complejidad del algoritmo. Se puede identificar a la constante 5 que multiplica a $n$ como $c_1$ y a la constante $-2$ como $c_2$, $T(n) = c_1n + c_2$:
$$T(n) = c_1n + c_2 \Rightarrow O(c_1n) = O(n)$$

En el caso de LinearSearch, el mejor caso es cuando el elemento $iX$ se encuentra en la primera posición del arreglo, entonces $T(n) = c_1 \Rightarrow O(1)$. El caso promedio es $T(n) = c_1\frac{n}{2} + c_2 \Rightarrow O(\frac{n}{2})$ y el peor caso (calculado previamente) es de $O(n)$.

%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Búsqueda Binaria}

El algoritmo de búsqueda binaria consiste en encontrar un valor dentro de un arreglo ordenado de valores de dicho tipo. La idea es buscar la posición central del espacio de búsqueda e ir comparando su valor dado que los valores están ordenados, si es mayor se busca en la mitad superior, si es menor en la mitad inferior.

\begin{lstlisting}[upquote=true, language=pseudo, numbers=left]
Const Integer N = ...
Const Integer NOT_FOUND = ...
Array aArr of Integer [1..N]
function BinarySearch(Array aA of Integer [], Integer iN, iX)	//iX es el elemento a buscar
  Integer iI = 1
  while iI <= iN do
    Integer iHalf = (i + iN) div 2
    if iX == aA[iHalf] then
      return iHalf
    elseif iX > aA[iHalf] then
      iI = iHalf
    else
      iN = iHalf
  end
  return NOT_FOUND
end
//inicialización de aArr con valores
//asignación del valor a buscar en el arreglo y almacenarlo en iX
Print(BinarySearch(aArr, N, iX))
\end{lstlisting}

Tal como se menciono anteriormente, solo se tomará en cuenta el cuerpo de la función sin tomar en cuenta los parámetros de éste. Así, la función $T(n)$ de BinarySearch queda como:
$$T(n) = 1 + T(while) + T(Return - Linea15)$$

El primer valor corresponde a la instrucción de la línea 5, $T(while)$ al ciclo que va desde la línea 6-14 y la instrucción de return de la línea 15, teniendo $T(n) = T(while) + 2$. Asumiremos nuevamente que $n = iN$ para los cálculos.

A diferencia que el caso anterior, el ciclo corresponde a un while donde los incrementos no son constante y varían en el transcurso del algoritmo. La condición $iI \le iN$ (línea 6) es quien regula el número de iteraciones. Así, es importante estudiar el comportamiento del número de iteraciones del ciclo (representado como $k$). En este caso, la variable $iI$ toma el valor de 1 y finaliza en $iN$ y durante su ejecución tanto $iI$ como $iN$ se modifican por el valor de $iHalf$, donde $iHalf$ es el punto medio entre dichos valores.

Dado que siempre se considera el peor caso, entonces se asume que el valor buscado siempre es mayor que cualquier elemento del arreglo y no se encuentra. Inicialmente $iI =1$, $iN = n$ y $iHalf = \frac{n+iI}{2}$ y mostrando el número de iteraciones $k$ se observa: 

\begin{table}[h]
\centering
\begin{tabular}{clc}
\hline
k    & \multicolumn{1}{c}{iI} & iN                     \\ \hline
$0$    & $1$                      & n                     \\
$1$    & $\frac{n}{2}$                    & n                     \\
$2$    & $\frac{n}{2} + \frac{n}{2}$              & n                     \\
$3$    & $\frac{n}{2} + \frac{n}{2} + \frac{n}{8}$        & n                     \\
$4$    & $\frac{n}{2} + \frac{n}{2} + \frac{n}{8} + \frac{n}{16}$ & n \\
...  & ...                    & ...                   \\
$log_2n$ & n                      & n
\end{tabular}
\end{table}

Realmente es indistinto si se modifica siempre el valor de $iI$ o $iN$, solo es importante el valor de $k$ de veces que se ejecuta. El número de veces se puede representar por la función $log_2$ basado en la entrada $n$. Entonces, dicho valor de $k$ será el número de veces que se ejecute el ciclo while.

Volviendo al cálculo de $T(while)$ queda entonces:
$$T(while) = 1 + \sum_{k=1}^{log_2n}{1 + T(Linea 7) + T(if/elseif)}$$

Para $T(Linea 7)$ se tiene una operación de suma, una división entera y una asignación. Es posible considerar el tiempo como 3, sin embargo según la regla 1 (ver \ref{lb:seccomp}) será $T(Linea 7) = 1$ quedando por calcular $T(if/elseif)$ de las líneas 8 -14. Dado que $T(if/elseif) = Max{2, 2, 1} = 2$ entonces $T(whiles)$ es:
\begin{eqnarray*}
T(while)&=&1 + \sum_{k=1}^{log_2n}{1 + 1 + 2}\\
&=&1 + \sum_{k=1}^{log_2n}{5}\\
&=&2 + 5 log_2n
\end{eqnarray*}

Si se emplea constantes para definir cada valor se tiene que $T(while) = c_1 + c_2 log_2n$ y para $T(n) = T(n) = T(while) + c_3$:
$$T(n) = c_1 + c_2 log_2n + c_3 \Rightarrow O(c_2 log_2n) = O(log_2n)$$

%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Bubble Sort}

El algoritmo de Bubble Sort es un algoritmo de ordenamiento que consiste en revisar cada elemento de un arreglo con el siguiente, intercambiándolos de posición si están en el orden equivocado. Este proceso se realiza varias veces hasta que no se necesiten más intercambios (ya estaría ordenado).

Muchas veces, resulta más sencillo estudiar la complejidad de un algoritmo examinando su estructura y luego, de forma conveniente, obtener los $T(n)$ de cada fragmento de código. Este ejemplo permite explorar este estilo:

\begin{lstlisting}[upquote=true, language=pseudo, numbers=left]
Const Integer N = ... 
Array aArr of Integer [1..N]
void BubbleSort(ref Array aA of Integer [], Integer iN)
  Integer iI, iJ
  for iI = 1 to iN - 1 do
    for iJ = iI + 1 to iN - 1 do
      if aA[iJ-1] > aA[iJ] then
        Integer iAux = aA[iJ-1]
        aA[iJ-1] = aA[iJ]
        aA[iJ] = iAux
      end
    end
  end
end
//inicialización de aArr con valores
BubbleSort(ref aArr, N)
\end{lstlisting}

Se puede observar que el algoritmo consta de dos ciclos for anidados (línea 5 y 6), y dentro del más interno está un condicional (línea 7). Entonces, para el segundo ciclo for es necesario calcular el condicional que lo contiene, y para el primer ciclo for se requiere calcular el segundo ciclo for. Por ello, empezaremos por calcular el condicional.

El condicional de la línea 7 es $T(if) = c_1 + T(Linea8-10)$, donde $c_1 = 3$ representa a las dos operaciones de acceso a memoria y la comparación. De hecho, estudiando el comportamiento de las líneas 8, 9 y 10 se puede decir que $T(Linea8-10) = 2 + 3 + 2 = 7$, pero asumiendo la misma premisa que la constante $c_1$ entonces $T(Linea8-10) = c_2$, por lo que $T(if) = c_1 + c_2 \rightarrow c$.

Una vez calculado el condicional, y examinando desde lo más interno de la estructura del algoritmo, corresponde calcular $T(2dofor) = c_3 + c_4 + \sum_{j=i+1}^{n}{c_4 + c + c_5)}$. Es posible agrupar las constantes para tener una mejor lectura y poder expandir la ecuación, entonces:
\begin{eqnarray*}
T(2dofor)&=&c_3 + c_4 + \sum_{j=i+1}^{n}{c_4 + c + c_5}\\
&=&c_6 + \sum_{j=i+1}^{n}{c_7}\\
&=&c_6 + (n-i){c_7}
\end{eqnarray*}

Ahora, se procede a calcular el primer ciclo for (línea 5):
\begin{eqnarray*}
T(1erfor)&=&c_8 + c_9 + \sum_{i=0}^{n-1}{c_9 + c_6 + (n-i){c_7} + c_{10}}\\
&=&c_{11} + (c_9 + c_6 + c_10)\sum_{i=0}^{n-1}{(n-i)c_7}\\
&=&c_{11} + c_{12}\sum_{i=0}^{n-1}{(n-i)c_7}\\
&=&c_{11} + c_{12}c_7 \sum_{i=0}^{n-1}{n-i}\\
&=&c_{11} + c_{12}c_7 \left[ \sum_{i=0}^{n-1}{n} - \sum_{i=0}^{n-1}{i}\right]\\
&=&c_{11} + c_{13} \left[ n(n-1) - \frac{n(n-1)}{2}\right]\\
&=&c_{14} \left[ n(n-1) - \frac{n(n-1)}{2}\right]\\
&=&c_{14} \left[ n^2-n \right]\\
&=&c_{14}n^2 - c_{14}n \Rightarrow O(Max\{c_{14}n^{2}, -c_{14}n\}) = O(c_{14}n^{2}) = O(n^{2})
\end{eqnarray*}
%\Rightarrow O(Max\{c_{14}n^{2}, -c_{14}n\}) = O(c_{14}n^{2}) = O(n^{2})

Por la regla del producto, el $T(n)$ de la función BubbleSort consiste en calcular solamente el primer ciclo for para obtener la complejidad del algoritmo completo. El nombre de las constantes es solo una forma de realizar el cálculo, es posible no agruparla e ir llevando la cada variable por separado o con su valor literal. Independientemente de dicho hecho, el resultado será el mismo para la complejidad $O(n^{2})$.

%%%%%%%%%%%%%%%%%%%%%%%
\section{Algoritmos}

Los siguientes algoritmos se presentan como buenos ejercicios para su cálculo de complejidad de algoritmos iterativos. Estos se presentan como fragmentos de código, ignorando en qué contexto son ejecutados (i.e. unidades invocables).

\begin{lstlisting}[upquote=true, language=pseudo]
Integer n, iX = 0
Read(n)
for Integer iI = 0 to iN do
  for Integer iJ = 0 to iI*iI do
    for Integer iK = 0 to iJ do
      iX = iX + 2
    end
  end
end
\end{lstlisting}

El algoritmo anterior tiene una complejidad de $O(n^{5})$. Considere que el valor límite del segundo ciclo es $iI^{2}$ el cual pertenece al primer ciclo que va desde el valor $0$ hasta $n$ (variable $iN$).

\begin{lstlisting}[upquote=true, language=pseudo]
for Integer iI = 0 to iN-1 do
  Integer iJ = 0
  while iI < iN do
    iJ = iJ + 1
    iI = iI + 1
  end
  if iJ < iN then
    for Integer iK1 = 0 to iN do
      for Integer iK2 = 0 to iN do
        iI = iK1 * iK2
      end
    end
  end  
end
\end{lstlisting}

En este fragmento de código el punto interesante radica sobre la variable $iI$ y el ciclo for de la línea 1. Dicho ciclo solo se ejecutará 1 sola vez. En este caso, el ciclo de la línea 8 es quién determinará la complejidad total del fragmento de código $\rightarrow$ $O(n^{2})$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Complejidad de Algoritmos Recursivos}

En el cálculo de la complejidad de algoritmo iterativos, su tiempo de ejecución viene dado por el número de operaciones elementales que se ejecutan. Sin embargo, para los algoritmos recursivos existe con una dificultad extra pues la función que establece su tiempo de ejecución viene dada por una ecuación en recurrencia, es decir, $T(n) = F(n)$ en donde en la expresión $F(n)$ aparece la propia función $T$.

Resolver tal tipo de ecuaciones consiste en encontrar una expresión no recursiva de $T$. Por lo general, encontrar dicha función no es tarea sencilla. Veamos un ejemplo de una función recursiva de nombre $LessInArray$ que calcular el menor valor en un arreglo del tipo Integer de forma recursiva.

\begin{lstlisting}[upquote=true, language=pseudo, numbers=left]
const Integer N = ...
const Integer MAX_INTEGER = ...
function LessInArray(Array aArray of Integer[], Integer iN)
  if iN <= 0 then
    return MAX_INTEGER
  else
    Integer iValue = LessInArray(iN - 1)
    if aArray[iN] < iValue then
      return aArray[iN]
    else
      return iValue
    end
end

Array aArray of Integer[1..N]
fillArray(ref aArray)	//filled with positive numbers
Print (LessInArray(aArray, N))
\end{lstlisting}

Se observa que es un algoritmo simple que recorre desde la posición $N$ del arreglo hasta la posición $1$, haciendo invocaciones con la posición a la cual se va a acceder, $N-1$, $N-2$, $\dots$, $N-k$, $\dots$, $1$.

Haciendo análisis del algoritmo podemos notar que posee una invocación recursiva. Si aislamos dicha instrucción (línea 7), el resto del algoritmo tiene comportamiento constante. Considerando la invocación recursiva, para un tamaño de entrada $N$ se tiene $T(n)$, sin embargo la instrucción hace que la función $T$ se comporte como $T(n) = T(n-1) + c$, donde $c$ es una constante. El tamaño del espacio de búsqueda se reduce en $1$ con respecto a la invocación original (ver la sección \ref{lb:recursi}, parte II sobre invocaciones recursivas) y se hace una operación de asignación de costo constante, $c$.

De esta forma, es posible escribir la función $T(n)$ de la siguiente forma:

\begin{equation}
T(n) = \left\{
  \begin{array}{l l}
    c_1 & \quad \text{si $n \le 0$}\\
    T(n-1) + c_2& \quad \text{si $n \ge 1$}
  \end{array} \right.
 \end{equation}
 
 Cuando $n \le 0$ (línea 4) entonces el valor corresponde a una constante $c_1$ y, en caso de que $n \ge 1$ se corresponde a la invocación recursiva por una ecuación de recurrencia de $T(n)$. En este punto, queda estudiar como es el comportamiento de $T(n)$ cuando $n \ge 0$ dado que el espacio de búsqueda se reduce. Para ello tenemos que:

\begin{eqnarray*}
T(n)&=&T(n-1) + c_2\\
&=&\left [ T(n-2) + c_2\right ] + c_2 = T(n-2) + 2c_2\\
&=&\left [ T(n-3) + c_2\right ] + 2c_2 = T(n-3) + 3c_2\\
&=&\dots\\
&=&T(n-k) + kc_2\\
\end{eqnarray*}

Es posible sustituir el valor de $T(n - i)$ por la correspondiente función $T$ a $T(n - i - 1) + c_2$, y aplicar este proceso $k$ veces, tal que se obtiene de forma general $T(n - k) + k_c2$.

El número $k$ representa el número de veces que se ejecuta dicho algoritmo, o el número de veces que se realizan invocaciones recursivas. Ahora, ¿para qué interesa conocer el número de veces que se ejecuta?. Al conocer este detalle, y expresando la función $T(n)$ en función de $k$, es posible determinar cuándo terminará de ejecutarse el algoritmo. Así, es importante conocer cuando dicha recurrencia llegará al caso cuando $n \le 0$ y se pueda obtener la complejidad $c_1$ multiplicado por un número $k$ de veces.

Para que $T(n-k)$ sea $T(n=0)$ se debe cumplir que:
$$n - k = 0 \Rightarrow n = k$$

Tomando este aspecto, es posible re-escribir nuevamente la función de recurrencia y probar con $n-k$ y determinar cuántas veces se ejecutará. Entonces, sustituyendo se tiene que:

\begin{eqnarray*}
T(n)&=&T(0) + nc_2\\
&=&c_1 + nc_2 \Rightarrow O(n) \\
&\Rightarrow O(n)
\end{eqnarray*}

La función $T(n)$ arroja que el tiempo de ejecución es $c_1 + nc_2$, por lo tanto, su complejidad es $O(n)$.

\subsection{Clase de Recurrencia}

Existen algunos tipos concretos de ecuaciones en recurrencia que su solución es conocida, que se dan con más frecuencia al estudiar el tiempo de ejecución de los algoritmos recursivos\footnote{En este documento no se presenta la clasificación de ecuaciones de recurrencia homogéneas y no homogéneas}. En términos generales, la idea es expresar el valor de una función para un cierto valor $n$ en función de los valores de la función para $n's$ de menor tamaño.

De forma simple, existen dos teoremas que son una solución general para una clase de recurrencia:

\textbf{Teorema \#1}: Sean $a, b, c$ constantes no negativas, la solución de la recurrencia:
\begin{equation}
T(n) = \left\{
  \begin{array}{l l}
    cn^{k} & \quad \text{si $1 \le n < b$}\\
    aT(n/b) + cn^{k}& \quad \text{si $n \ge b$}
  \end{array} \right.
 \end{equation}
 
\noindent donde $a$ es el número de subproblemas, $n/b$ el tamaño de cada uno de los subproblemas.

Particularmente, si $n$ es potencia de $b$ se cumple que:
\begin{equation}
T(n) = \left\{
  \begin{array}{l l}
    O(n^{k}) & \quad \text{si $a < b^{k}$}\\
    O(n^{k}logn) & \quad \text{si $a = b^{k}$}\\
    O(n^{log_b a}) & \quad \text{si $a > b^{k}$}
  \end{array} \right.
\end{equation}

\textbf{Teorema \#2}: Sean $a, b, c$ constantes no negativas, la solución de la recurrencia:
\begin{equation}
T(n) = \left\{
  \begin{array}{l l}
    cn^{k} & \quad \text{si $1 \le n \le b$}\\
    aT(n-b) + cn^{k}& \quad \text{si $n > b$}
  \end{array} \right.
 \end{equation}
 
\noindent donde $a$ es el número de invocaciones recursivas que se realizan y $n-b$ el tamaño de cada una.

Particularmente, si $n$ es divisible entre $b$ se cumple que:
\begin{equation}
T(n) = \left\{
  \begin{array}{l l}
    O(n^{k}) & \quad \text{si $a < 1$}\\
    O(n^{k+1}) & \quad \text{si $a = 1$}\\
    O(n^{a^{k div b}}) & \quad \text{si $a > 1$}
  \end{array} \right.
\end{equation}

%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Ejercicios}

Un ejemplo simple y bien conocido es la búsqueda binario. Se puede escribir la función como:

\begin{lstlisting}[upquote=true, language=pseudo]
Const Integer N = ...
Const Integer NOT_FOUND = ...
Array aArr of Integer [1..N]
function BinarySearch(Array aA of Integer [], Integer iX, iLow, iHigh)
  if iLow > iHigh then
    return NOT_FOUND
  end
  Integer iHalf = (iLow + iHigh) div 2
  if iX == aA[iHalf] then
    return iHalf
  elseif iX > aA[iHalf] then
    return BinarySearch(aA, iX, iHalf + 1, iHigh)
  else
    return BinarySearch(aA, iX, iLow, iHalf - 1)
  end
end
//inicialización de aArr con valores
//asignación del valor a buscar en el arreglo y almacenarlo en iX
Print(BinarySearch(aArr, iX, 1, N))
\end{lstlisting}

Examinando el algoritmo, es posible deducir la función $T(n)$ como:

\begin{equation}
T(n) = \left\{
  \begin{array}{l l}
    c_1 & \quad \text{si $n \le 1$}\\
    T(n/2) + c_2& \quad \text{si $n > 1$}
  \end{array} \right.
\end{equation}

Es importante destacar que en algunos casos, como el algoritmo presentado, es posible separar la condición base y la condición recursiva y así determinar de forma sencilla la forma de $T(n)$. Una vez expresada la función $T(n)$ queda estudiar su comportamiento y expresarla en función del número de veces que se ejecuta, el número de $k$ veces. Realizando este procedimiento por sustitución queda:

\begin{eqnarray*}
T(n)&=&T(n/2) + c_2\\
&=&\left [ T(n/4) + c_2\right ] + c_2 = T(n/4) + 2c_2\\
&=&\left [ T(n/8) + c_2\right ] + 2c_2 = T(n/8) + 3c_2\\
&=&\left [ T(n/16) + c_2\right ] + 3c_2 = T(n/16) + 4c_2\\
&=&\dots\\
&=&T(n/2^k) + kc_2\\
\end{eqnarray*}

Teniendo la representación general de $T(n)$, queda determinar en qué punto dichas iteraciones alcanzan $n=1$ (cuando $n/2^{k} = 1$). Así se obtiene:
$$2^{k} = n \Rightarrow k = log_2(n)$$

Sustituyendo en la ecuación original se puede determinar el tiempo $T(n)$ del algoritmo.

\begin{eqnarray*}
T(n)&=&T(n/n) + log_2(n)\\
&=&c_1 + log_2(n)c_2 \Rightarrow O(log_2n) \\
\end{eqnarray*}

Finalmente, el orden de complejidad del algoritmo de búsqueda binaria es $O(log_2n)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Ideas Finales}
\begin{itemize}
\item La complejidad de un algoritmo depende del tamaño del problema que se presenta al momento de ser ejecutado
\item La complejidad hace referencia a cuánto tiempo se tomará en ejecutarse un algoritmo (comportamiento práctico y teórico)
\item Se estudian tres comportamientos de los algoritmos: peor caso, caso promedio y mejor caso. Para ello se requiere el cálculo de la cantidad de instrucciones que contiene el algoritmo, $T(n)$ y de acuerdo a su comportamiento asintótico obtener el orden $O$
\item El cálculo de la complejidad de algoritmos recursivos no es una tarea trivial. Por ello, se suele utilizar funciones de recurrencia conocidas con el fin de ajustar el comportamiento de un algoritmo a una de dichas funciones.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Problemas}
\begin{enumerate}
\item ¿Bajo qué criterios se considera un algoritmo de orden constante? ¿y de orden polinomial?
\item Calcule la complejidad del siguiente fragmento de código:
\begin{lstlisting}[upquote=true, language=pseudo]
Integer x = 0
for Integer i = 0 to n do
  for Integer j = 0 to i do
    for Integer k = 0 to j*j do
      x = x + 2
    end
  end
end
 \end{lstlisting}
\item Dado un arreglo desordenado de valores del tipo Real, se desea implementar una operación selectora, que dado un parámetro $k$, retorna el valor correspondiente a la posición $k$ del arreglo si este estuviera ordenado (\textbf{sin ordenarlo}). Defina un algoritmo que sea eficiente que dado cierto $k$ y cualquier arreglo, el tiempo de búsqueda sea el mismo. Calcule formalmente la complejidad en tiempo del programa.
\item Calcule la complejidad del siguiente algoritmo:
\item Dada la siguiente unidad invocable:
\begin{lstlisting}[upquote=true, language=pseudo]
void Beta()
  Integer  N, X, Y, Z, M
  X=0; Y=0; Z=0;
  Read (N)
  M = 2^N
  for Integer I = 1 to M do
    X = X + 1
    Y = Y + (3 * I)
    Z = (2*I) + 6 + Z;
  end
  Print (X); Print (Y); Print (Z); 
end
 \end{lstlisting}
 Se quiere que calcule la función $T(n)$ asociada a la función Beta y calcule su complejidad. Igualmente, re-escriba el algoritmo para que su complejidad sea $O(1)$. obteniendo los mismos resultados
 \item Si la complejidad de un algoritmo recursivo tiene el mismo orden de complejidad que su implementación de forma iterativa, ¿el número de iteraciones es igual? ¿el espacio que ocupan en memoria es el mismo?
 \item Calcule de forma detallada la complejidad para la siguiente función recursiva:
\begin{lstlisting}[upquote=true, language=pseudo]
function Epsilon (Integer iN) : Integer
  Integer iX, iI, iJ
  if n <= 1 then return 1
  else
    iX = Epsilon(iN div 2) + Epsilon(iN div 2)
    for iI = 1 to iN do
      for iJ = 1 to iN do
        iX = iX + iJ
      end
    end
    return iX
  end
end
\end{lstlisting}
\item Considere el siguiente algoritmo:
\begin{lstlisting}[upquote=true, language=pseudo]
function Weirdo (ref Array a of Integer [ ], Integer prim, Integer ult) : Integer 
Integer mitad, terc
  if prim>=ult then 
    return a[ult] 
  end
  mitad =(prim+ult) div 2
  terc = (ult-prim) div 3
  return a[mitad] + Weirdo(a, prim, prim+terc) + Weirdo(a, ult-terc,ult)
end
\end{lstlisting}
Se quiere que calcule el tiempo de ejecución de la invocación a la función \textit{Weirdo(ref a,1,N)} suponiendo que $N$ es potencia de 3. De una cota de complejidad para dicho tiempo de ejecución.
\end{enumerate}