utilizar el método de sustitución para demostrar que una ecuación está en O(n log2 n)

Question

Estoy tratando de demostrar que la ecuación:

T(n) = 2T((n/2) +17) + n es O(n log_2(n))

Tengo que hacerlo mediante el método de sustitución, pero estoy atascado en un paso.

He llegado a un punto en el que:

T(n) <= 2(c((n/2) +17) * log_2((n/2) +17) ) + n 

Estoy atascado bc no sé cómo simplificar el registro, o Si al hacer el método de sustitución, si se supone que debo usar ((n/2) + 17) para enchufar a n.

Se agradece la ayuda.

Answer 1

Muy bien, en primer lugar, necesitamos una forma de decrementar a través de la secuencia. Supongamos que $T(0)$ es el caso base.

Entonces, $T(0) = 2T(17) = 2^2T(\frac{51}{2}) + 2(17) = 2^3T(\frac{119}{4}) + 2(51 + 17) = 2^4T(\frac{255}{8}) + 2(119 + 51 + 17)$

Así que ahora tenemos un patrón.

$$T(0) = 2^{n+1}T(\frac{17\sum_{k=0}^{n}{2^k}}{2^{n}}) + 34\sum_{m=0}^{n-1}\sum_{k=0}^{m}{2^k} .$$

$$ T(0) = 2^{n+1}T(\frac{17(2^{n+1} - 1)}{2^n}) + 34(-n + 2^{n+1} - 2) $$

Fíjate que esto no tiene ningún sentido.

Eso es porque tu pregunta no tiene sentido. No puedes definir una secuencia en términos de términos posteriores, porque la recursión se extenderá hasta el infinito.