Estructuras de datos: Complejidad dada unas líneas de código

Si veis algún error, por favor, hacédmelo saber para corregirlo.

Nota: me he basado en las explicaciones de un usuario del foro www.urjavac.com al cual le doy las gracias por haberme explicado el ejercicio y su explicación, de alguna manera, está recogida en este post.

Existe una variante que en lugar de ser T(n-b) (caso por reducción) es T( n/b ) (caso por división).

En el caso 0<=n<=b:

cn^k --> Complejidad en el caso NO recursivo de las operaciones NO recursivas.

En el caso n>b:

cn^k --> Complejidad en el caso recursivo de las operaciones NO recursivas.

a --> Número de llamadas recursivas.

b --> Número de veces en el que se reduce/divide el problema con cada llamada recursiva.

Ejemplo:

FUNCTION Factorial (n: Integer): Integer; 
BEGIN  
IF (n = 0) OR (n = 1) THEN  
Factorial:= 1  
ELSE  
Factorial:= n * Factorial (n-1) 
END;

Hacemos la ecuación de recurrencias:

En este caso utilizaré el método por reducción, ya que tengo T(n-1). Si tuviese, por ejemplo, T(n/2) utilizaría el método por división.

• ¿Cuál es la complejidad en el caso NO recursivo de las operaciones NO recursivas? O(1), es decir, cn^k = 1 ya que se trata de una asignación.
• ¿Cuál es la complejidad en el caso recursivo de las operaciones NO recursivas? O(1), es decir, cn^k = 1. Ojo, el cn^k del caso base y el cn^k del caso recursivo no tienen por qué ser iguales.
• ¿Número de llamadas recursivas? 1, por lo que a = 1.
• ¿Número de veces en el que se reduce/divide (en este caso, reduce) el problema con cada llamada recursiva? 1, es decir, b=1.

Por lo que la ecuación de recurrencias para este caso es:

1. Expandimos k veces (iteraciones):

Comentario: Yo hago 3 iteraciones (k=3) pero podéis hacer todas las que queráis.

T(n) = T(n-1) + 1
T(n-1) = T( (n-1) - 1 ) + 1 = T(n-2) + 1
T(n-2) = T( (n-2) - 1 ) + 1= T(n-3) + 1

2. Sustituimos desde la última expansión hacia la anterior, y así sucesivamente hasta llegar a la primera de todas:

Como T(n-2) = T(n-3) + 1, entonces:

T(n-1) = [T(n-3) + 1] + 1 = T(n-3) + 2

T(n) = [T(n-3) + 2] + 1 = T(n-3) + 3

3. Generalizamos

T(n) = T(n-k) + k 

4. Tras k iteraciones, llegamos al caso recursivo (en este caso, a que n sea igual que 1):

n-k = 1

5. Despejamos k:

n=1+k ; n-1=k

6. Sustituimos k en nuestra ecuación generalizada:

T(n) = T( n - (n-1) ) + (n-1)
T(n) = T(1) + (n-1)

T(n) = 1 + n - 1 = n

7. La complejidad final de este código es:

T(n) = O(n)

--> -->