¿Prueba Big-O para una relación de recurrencia?

Esta pregunta es bastante específica en la forma de los pasos tomados para resolver el problema.

Dado prueba que . $T(n)=2T(2n/3)+O(n)$ $T(n)=O(n^2)$

Entonces los pasos fueron los siguientes. Queremos demostrar que . $T(n) \le cn^2$

\begin{aligned} T (n) & = 2 T (2 n / 3) + O (n) \\ \leq 2 c (2 n / 3)^{2} + a n \\ \leq (8 / 9) (c n^{2}) + a n \end{aligned}

$\begin{align*} T(n)&=2T(2n/3)+O(n) \\ &\leq 2c(2n/3)^2+an\\ &\leq (8/9)(cn^2)+an \end{align*}$ y luego mi profesor continuó:

T (n) \leq c n^{2} + (a n - (1 / 9) c n^{2}),

$T(n) \leq cn^2+(an-(1/9)cn^2)\,,$ que sale a:

T (n) \leq c n^{2} for any c >= 9 a .

$T(n)\leq cn^2 \text{ for any }c >= 9a\,.$

Mi pregunta es, ¿cómo pudieron cambiar de 8/9 a 1/9 al introducir un nuevo término? ¿Esto está permitido? Ella nunca explicó, esto solo estaba en sus soluciones.

asymptotics recurrence-relation D. Johnson
fuente

No veo un nuevo término introducido? Tenemos que

c n^{2} + a n - (1 / 9) c n^{2}

$cn^2 +an - (1/9)cn^2$ simplifica a

(8 / 9) c n^{2} + a n

$(8/9)cn^2 + an$ como en la línea anterior. Entonces las dos líneas son en realidad iguales. Tal vez te estás preguntando por qué uno podría querer hacer esto.

user340082710

También estoy asumiendo que la línea final debería leer

c n^{2}

$cn^2$ en lugar de

c k^{2}

$ck^2$ .

user340082710

@ZacharyFrenette Ah, tienes razón. en ese caso, no estaba seguro de cómo hizo la simplificación. ¿Por qué elegiría separar los términos de esa manera? Hay muchas formas de dividir (8/9). Creo que sé por qué uno querría hacer esto, para anular ese extra de ? De lo contrario, la desigualdad no se mantendrá. También gracias por señalar el error tipográfico, se solucionará. Si desea comentar como respuesta, puedo aceptarlo.

a n

$an$

D. Johnson

¿Prueba Big-O para una relación de recurrencia?

Respuestas: