Buenas, tengo el siguiente ejercicio resuelto, pero hay algunas cosas que no entiendo, escribo el ejercicio y explico posteriormente mis dudas:
Determinar el orden de complejidad de la siguiente función recursiva:
\( T(n) = 5T(n-1) - 8T(n-2) + 4T(n-3) +3+n^2 + n2^n \)
Solución:
Aplicamos el método general de resolución de recurrencias. Primero pasamos los términos con T del lado derecho al izquierdo y expresamos el resto de términos de la derecha como polinomios por potencias elevadas a n:
\( T(n)-5T(n-1)+8T(n-2)-4T(n-3) = (3+n^2)1^n + n2^n \)
Luego continúa pero el resto lo entiendo bien, el problema es este paso.
Mi duda es, por un lado, no entiendo lo de poner potencias elevadas a n. Es decir, pasa de esto:
\( T(n) =... 3+n^2 + n2^n \)
a esto:
\( ... (3+n^2)1^n + n2^n \)
No entiendo como puede hacer esa potencia, entiendo que debería multiplicar a todo, en ambos lados de la igualdad.
Mi segunda pregunta, va relacionada con la manera de resolver estas recurrencias, así que explico el método y luego mi duda.
Básicamente, la manera de resolver una recurrencia este tipo es (según mis apuntes) la siguiente:
Recurrencia general:
\( a_oT(n) +a_1T(n-1) + ... +a_kT(n-k) = b_1^n P_1^{d_1}(n)+...+b_s^n P_s^{d_s}(n) \)
Ecuación característica:
\( a_0x^k + a_1x^{k-1}+...+ a_k)(x-b_1)^{d_1+1} ... (x-b_s)^{d_s+1} = 0 \)
La pregunta es, dado que tengo que buscar en los terminos no afectados por las T una b y una d que cumpla la relación expresada aquí: \( b_1^n P_1^{d_1}(n)+...+b_s^n P_s^{d_s}(n) \)
Es posible descomponer un polinomio tipo:
\( an^2 +bn + c \)
en suma de dos polinomios:
\( P1 = an^2 \)
\( P2 = bn + c \)
