Resolver la ecuación recursiva $T(n)=T(k)+T(n-k-1)+O(n)$

Question

La pregunta está clara en el título. Estoy tratando de resolver esta recursividad como parte de mostrar que el peor caso de algoritmo de ordenación rápida ocurre cuando$k=0$, pero no puedo hacerlo. Podría hacer los siguientes casos específicos (usando repetidamente la misma recursividad):

1)$T(n)=T(n-1)+O(n)$
2)$T(n)=2T(\frac n2)+O(n)$

¿Alguien puede ayudarme a resolver este caso general (o al menos sugerir alguna otra forma de demostrar que el peor de los casos es $k=0$)?

PD : No conozco el teorema de Master, por lo que agradecería una solución sin usar eso (en caso de que sea aplicable aquí).

Answer 1

Considere la recurrencia $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$que es una formalización del peor tiempo de ejecución de quicksort. Demostremos por inducción que el máximo se alcanza en$k = 0$ (o $k = n$). Mostraremos esto y al mismo tiempo mostraremos que$T(n) = \frac{n(n+1)}{2}$.

El caso base, $n=0$, es claro. Ahora suponga que$T(m) = \frac{m(m+1)}{2}$ para todos $m \leq n$y considerar $T(n+1)$. La función$T(k)$ es convexo en el intervalo $[0,n]$ (lo ampliamos a valores reales usando la misma fórmula), por lo que el máximo de $T(k) + T(n-k)$ se alcanza en $k=0$ (o $k=n$). Por lo tanto$$ T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}. $$

En lugar de argumentar usando convexidad, también podemos argumentar directamente: $$ T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} = \frac{n(n+1)}{2}-k(n-k), $$ que se maximiza claramente (de forma única) cuando $k = 0$ o $k = n$.