Resuelve la ecuación T (n) = a T (n-1) + c para n> 0, usando recurrencia? . ¿Cuál es la complejidad de la ecuación dada T (0) = k?

Es probable que esta sea una pregunta de tarea, por lo que me limitaré a proporcionar un método sin dar una respuesta. La primera observación que se debe hacer es que el uso del teorema maestro no proporciona ninguna pista real. Sin embargo, debería poder resolver esto desde los primeros principios.

Comience con esto:

Considere por un momento lo que sucedería si dejamos c = 0.

Entonces esto es solo

T (n) = aT (n-1)

Como T (0) = k, ahora vemos que T (1) = a * k.

Como T (1) = a * k, podemos ver que T (2) = a * T (1) = a * a * k = a ^ 2 * k

Similar:

T (3) = a * T (2) = a * a ^ 2 * k = a ^ 3 * k

¿Puedes ver un patrón?

En general, si suponemos que T (n) = a ^ n * k, podemos mostrar que T (n + 1) = a ^ (n + 1) * k.

Genial, esto resuelve el problema con c = 0. Suponiendo que c> 0, ahora tenemos * límites inferiores * para el posible valor de la relación.

También podemos obtener límites superiores dejando que c = T (n-1). En cuyo caso, la ecuación se convierte en:

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

Siguiendo la lógica que hicimos antes, podemos ver que esto será T (n) = (a + 1) ^ n * k.

Entonces, ahora tenemos límites superiores y límites inferiores. Si obtiene un resultado fuera de estos límites, sabe que hizo algo mal.

Ahora, finalmente, considere el caso en cuestión:

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

Bueno, podemos ver que:

T (1) = a * T (0) + c = a * k + c

T (2) = a * T (1) + c = a * (a * k + c) + c = a ^ 2k + ac + c = a ^ 2k + (a + 1) c

T (3) = a * T (2) + c = a * (a ^ 2k + (a + 1) c) + c = a ^ 3k + (a ^ 2 + a + 1) c

Si aún no ve un patrón, intente esto un par de pasos más para obtener T (4) y T (5). Tenga en cuenta también que probablemente desee la respuesta en notación Big-O, así que ignore las partes “insignificantes” del resultado.