Comencemos por analizar la función factorial. Definiremos un algoritmo recurrente para la misma utilizando la notación de pseudocódigo.
Notemos que el caso base ocurre cuando la entrada 'n' es igual a 0 o a 1.
Luego se produce la llamada recursiva decrementando el tamaño de la entrada en una unidad. Esto nos indica que estamos en presencia del Caso 1.
Recordamos del Capítulo 2 que para este caso, el orden de la función venía dado por la relación entre 'a' (la cantidad de veces que se llama la función recursiva) y 1
Como se puede apreciar, aquí realizamos una única vez la llamada recursiva (pues la misma no se encuentra dentro de un bucle), siendo a = 1 entonces.
Nos resta determinar el valor de 'k', el grado del polinomio p(n)
A simple vista podemos ver que existe una única instrucción además de la llamada recursiva, y la misma tiene un valor constante (se devuelve un valor). Por lo tanto, el polinomio p(n) es una constante y finalmente k = 0.
Este análisis nos lleva a determinar el orden la función factorial recursiva en O(n)
A continuación analizaremos la complejidad temporal de ejemplos generales, sin entrar en detalles de qué propósito cumple el algoritmo.
Ejemplo 1
Se da como dato que el orden del método "calcularCondicion" es O(log n) y el orden del método "procesar" es O(n)
Este ejemplo se enmarca dentro del caso 2 ya que el tamaño de la entrada es dividido (en este ejemplo por 3).
El análisis de complejidad temporal queda:
a = 1 ya que existe una única llamada recursiva. Que no nos confunda el hecho que veamos tengamos la llamada en dos bloques si distintos. Precisamente, por cada instancia de ejecución del método 1 se ejecutará, o bien las instrucciones dentro del bloque 'si', o bien las instrucciones dentro del bloque 'sino', pero nunca se ejecutarán ambas. Por ello a = 1.
Queda claro que b = 3, pues es la cantidad que divide a la entrada
Sólo resta determinar el valor de k. Por los datos proporcionados vemos que la función procesar tiene orden O(n) y la función calcularCondicion O(log n). Siendo n mayor a log n consideraremos el peor de los casos, o sea, O(n). Esto hace que k = 1.
Resumiendo, debemos ver la relación entre a y bk siendo a = 1, b = 3 y k = 1.
Claramente a < bk ya que 1 < 3.
Finalmente tenemos que el orden del Método 1 es O(nk) = O(n)
NOTA: si no existiera la función "procesar", la única función no afectada por la recursividad sería calcularCondicion con un orden O(log n). En dicho caso, debe hacerse el análisis para k = 0 y también k = 1, quedándonos con el que arroje el peor resultado.
Ejemplo 2
Se da como dato que el orden los métodos "calcularCondicion" y "procesar" es O(c), es decir, constantes.
A diferencia del método anterior, aquí podemos ver que existen 2 llamadas recursivas en un único bloque, por lo tanto a = 2.
La entrada se divide en dos, resultando b = 2 y como "calcularCondicion" y "procesar" son ambos métodos constantes, k = 0
Como la entrada es dividida estamos en presencia del caso 2
La relación es a > bk siendo el orden O(nlogba), reemplazando los valores nos queda O(n)
Ejemplo 3
Se da como dato que el orden del método "calcularValor" es constante y el orden del método "procesar" es O(n*log n)
Este ejemplo se encuadra en el caso 1 ya que se sustraen elementos de la entrada. Tenemos dos llamadas recursivas, por ende, a = 2. La entrada disminuye en un elemento, por ello, b = 1.
Para el valor de k, el método procesar tiene un O(n*log n) pero notemos que está incluido dentro de un bloque mientras (comunmente llamado while). Entonces debemos multiplicar este orden por la cantidad de veces que se ejecute el bloque. En el peor de los casos, el bloque se ejecutará n veces (ya que ingresa mientras val < n). Por lo tanto el costo del bloque será n * n*log n.
Aquí debemos entonces analizar qué pasa en los casos que k = 2 y k = 3 y quedarnos con el peor.
Vemos que a = 2 es mayor a 1, por ello estamos en presencia de un costo del orden O (an div b),
resultando en una complejidad exponencial O(2n)
