Demostrar por inducción de que la forma de recurrencia de tipo de burbuja es $ \ OMEGA (N ^ 2) $

Question

La forma de recurrencia de tipo de burbuja es $ t (n)= t (n-1) + n- 1 $

¿Cómo puedo probar por inducción que esto es $ \ omega (n ^ 2) $ ?

Estoy atascado con $ t (n + 1) \ geq cn ^ 2 + n= n (cn + 1) $

Answer 1

Suponiendo $ t (1)= 1 $ , puede mostrar por inducción que $ t (n)= \FRAC {N (N-1)} {2} + 1 $ .

El caso base es trivial desde $ t (1)= 1=frac {1 \ cdot 0} {2} + 1 $ .

En cuanto a la etapa inductiva, suponga que la reclamación se celebra hasta $ t (n) $ . $ \ comienzan {align *} T (n + 1) &= t (n) + (n + 1) - 1=frac {n (n-1)} {2} + 1 + n \\ &=frac {n ^ 2 -n + 2n} {2} + 1=frac {n ^ 2 + n} {2} + 1=frac {n (n + 1)} {2} + 1 \\ &=frac {(n + 1) ((N + 1) - 1)} {2} + 1. \ End {align *} $